codeforces 338 E. Optimize! (线段树维护最小前缀和）
题意：题意是由伪代码给出的。。手算模拟了一下(noip初赛即视感），题意大概是说，给出两个数组a和b，a数组长度为n,b数组长度为len,然后从a中截取连续的len个元素，称为数组s，如果存在一种方法使得s中元素和b中的元素一一对应且每组和都大于等于h,则称这个s是合法的。现在问a中有多少个合法的s。 具体来说，对于样例 5 2 10 5 3 1 8 5 5 7
s={8,5}和s={5,7}是有解的。 因为对于前者8+3>=10并且5+5>=10,对于后者5+5>=10,7+3>=10,因此答案为2 思路：
最重要的一部是，我们先将b排序，然后维护一个函数f[i],在排序后的b中找到一个最小的j，满足a[i]+b[j]>=h,然后让f[i]=j?
f[i]直接二分就可以得到。。
因为f[i]的值是使得a[i]满足条件的最小的b值。
然后我们观察发现。
f[i]大于等于len的元素个数最多有1个，不然无解。
f[i]大于等于len-1的元素个数最多有2个，不然无解。
f[i]大于等于i的元素个数最多由len+1-i个，不然无解。
设g[i]=len+1-i-sum[i],sum[i]=y[i]+y[i+1]+...+y[len]。
如果某个s中，对于所有的i，都有g[i]>=0，那么这个s就是合法的。
实际上我们没有必要去查询每个g[i]，只要g[i]中最小的大于等于0，那么这个s就是合法的。
现在的问题就变成了动态维护一段长度为len的最小后缀和。
我的思路是整体覆盖，
当a数组的区间从[l,r]到[l+1,r+1]的时候，增加了a[r+1],假设f[r+1]=p,那么用线段树更新区间[1,p]，都增加1. 减少了a[l],假设f[l]=q,那么同样用线段树维护，使得区间[1,q]都减少1.
讲道理应该也可以做吧。。。
不过被羊神@sheep教育说其实单点更新就可以。。。
于是去学了下动态维护区间最大子段和的线段树做法： bzoj 1756解题报告hit oj 2687 解题报告
然后单点更新维护最大后缀和就很容易了。
类似的做法，我们也维护一个最小前缀和。初始化的时候把1..len赋值成-1.
然后每次移动区间，从【l,r】移动到[l+1,r+1]的时候，将f[r+1]添加1，将f[l]减少1.
这样如果某个s中的任意前缀和都是等于0的，那么这个s就是合法的。
因此我们只需要维护最小前缀和。
代码是维护的最小前缀和
1/* ***********************************************
2Author :111qqz
3Created Time :Fri 16 Sep 2016 05:13:38 PM CST
4File Name :code/cf/problem/338E.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=150005;
32int n,len,h;
33int a[N],b[N],f[N];
34struct Tree
35{
36 int mn;//最小前缀和
37 int sum;//区间和
38}tree[N<<2];
39void PushUp( int rt)
40{
41 tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
42 tree[rt].mn = min(tree[rt<<1].mn,tree[rt<<1].sum+tree[rt<<1|1].mn);
43}
44void build( int l,int r,int rt)
45{
46 if (l==r)
47 {
48 if (l<=len)
49 tree[rt].sum = tree[rt].mn = -1;
50 return;
51 }
52 int m = (l+r)>>1;
53 build(lson);
54 build(rson);
55 PushUp(rt);
56}
57void update( int p,int sc,int l,int r,int rt)
58{
59 if (l==r)
60 {
61 tree[rt].sum += sc;
62 tree[rt].mn +=sc;
63 return;
64 }
65 int m = (l+r)>>1;
66 if (p<=m) update(p,sc,lson);
67 else update(p,sc,rson);
68 PushUp(rt);
69}
70int bin( int x)
71{
72 int l = 1;
73 int r = len;
74 int res = len+1; //无穷。
75 while (l<=r)
76 {
77 int mid = (l+r)>>1;
78 if (b[mid]+x>=h)
79 {
80 r = mid-1;
81 res = mid;
82 }
83 else
84 {
85 l = mid+1;
86 }
87 }
88 return res;
89}
90int main()
91{
92 #ifndef ONLINE_JUDGE
93 freopen("code/in.txt","r",stdin);
94 #endif
95 ios::sync_with_stdio(false);
96 ms(tree,0);
97 cin>>n>>len>>h;
98 int siz = len+1;
99 for ( int i = 1 ;i <= len ; i++) cin>>b[i];
100 sort(b+1,b+len+1);
101 for ( int i = 1 ; i <= n ; i++)
102 {
103 int x;
104 cin>>x;
105 a[i] = bin(x);
106 }
107 build(1,siz,1);
108 for ( int i = 1 ; i < len ; i++) update(a[i],1,1,siz,1);
109 int ans = 0 ;
110 for ( int i = len ; i <= n ; i++)
111 {
112 update(a[i],1,1,siz,1);
113 if (tree[1].mn==0) ans++;
114 update(a[i-len+1],-1,1,siz,1);
115 }
116 cout<<ans<<endl;
117 #ifndef ONLINE_JUDGE
118 fclose(stdin);
119 #endif
120 return 0;
121}