nyoj-1316-二分

acm.nyist.edu.cn/JudgeOnline/problem.php?pid=1316题目链接

Interval

时间限制：2000 ms | 内存限制：65535 KB

难度：3

描述: 才发现编故事背景那么难，原谅当初语文考满分的我。

对于区间[L, R](L <= R)而言，它的长度是R - L + 1，区间和则是a[L] + ... + a[R]。

区间元素的下标是从1开始的。

如：序列{5 2 1 1 3 1 4}

区间[2 4]的长度是3，区间[2, 5]的区间和 = 2 + 1 + 1 + 3 = 7。

现在Ocean用程序随机生成了一个序列，该序列一共有N个整数。

对于这个序列，他想知道区间长度 >= L且满足区间和 >= M的不同区间有多少个？

对于两个区间[x1, y1]和[x2, y2]，若x1 != x2 或者 y1 != y2则可以认为两个区间是不同的。

输入

第一行输入一个整数T，代表有T组测试数据。
每组数据占两行，第一行依次输入三个整数N，L，M分别代表上面提到的信息。
下面一行输入N个整数ai。

注：1 <= T <= 100，1 <= L <= N <= 10000，-100000 <= M，ai <= 100000。

输出

对每组测试数据，输出一个整数代表最后的结果。

样例输入

3
1 1 1
1
4 2 3
1 2 3 4
6 3 -7
-1 -2 -3 4 -5 6

样例输出

1
6
10

来源

第七届河南理工大学程序设计大赛

上传者

liuyuqiang

一开始的思路是先将[1,L],[1,L+1]......[1,N]这几个区间push进容器中，然后每次固定一个起点，从1开始，显然我们可以让M每次加上起点之前的前缀和，抵消之后就等价于区间和变为了以当前起点为左边界的区间。然后二分查找满足条件的区间个数，同时每次都要把区间长度最小的那个区间pop出去，因为每次

区间长度都等价于自动减一(由于左边界的右移)。

但是在一个连续的有序序列中删除节点的复杂度是O(N)，可以逆向来想，我们从左边界的最大值开始枚举，慢慢的减小到1，这样前面满足的区间在后面依旧满足我们要做的是每次添加进去一个区间即可，添加时用了insert函数，复杂度按理说也是O(N),但stl还是比自己写的快把。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[10100],pre[10100];
 4 int main()
 5 {
 6     int T,L,M,N,i,j,k;
 7     cin>>T;
 8     while(T--){
 9         vector<int>q;
10         cin>>N>>L>>M;
11         for(i=1;i<=N;++i){
12             scanf("%d",a+i);
13             pre[i]=pre[i-1]+a[i];
14         }
15         int ans=0;
16         for(i=N;i>=L;i--){
17             int p=lower_bound(q.begin(),q.end(),pre[i])-q.begin();
18             q.insert(q.begin()+p,pre[i]);
19             vector<int>::iterator x=lower_bound(q.begin(),q.end(),M+pre[i-L]);
20                 ans+=q.end()-x;
21         }
22         cout<<ans<<endl;
23     }
24     return 0;
25 }