HPU 1193: Interval(查询区间长度大于特定值且区间和大于特定值的区间个数)

题意就是题目上说的那样。。。给出一个n个数的序列,对于这个序列询问区间长度\(>=L\)且满足区间和\(>=M\)的区间的个数。数组下标从\(1\)开始,\(N\leq 10000,-100000\leq M,a[i] \leq 100000\)。

很久之前和ClearY吃饭的时候讨论的,后来她居然弄到校赛里面去了。。。

维护出来一个前缀和,那么对于位置\(pos\)来说,对答案的贡献就是位置\(i\)满足\(i <= pos-L\),而且\(sum[pos]-sum[i] >= M\)。那么我们从前往后扫,维护一棵平衡树,对于每个位置\(i\)找到他往后的\(L\)个位置\(pos\),查询比\(a[pos]-M\)小于等于的数有多少个就好了。这个treap写个rank函数就好了。

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注