题意：题意是由伪代码给出的，手算模拟了一下（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}