转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
出题人题解没看懂。。。囧。
然后看了下tourist代码，很短，也很好理解。。。
我们将b排序之后，很显然如果组合的话肯定是贪心。
那么对于a的某个子串a'要满足条件的话，那么显然是所有的数和b中最大元素相加不小于h。
至少有len - 1个数的b中次大元素相加不小于h。。。以此类推那么首先预处理出对于a中的每个元素，和b串的哪些元素相加不小于h，显然是排序之后的二分
那么选中某个区间的数，就是一个区间覆盖，判断b中第i大元素是否至少被覆盖了i次。
为了方便，我们先将第i位减去一个i，然后判断区间最小值是否非负。
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define lson step << 1
#define rson step << 1 | 1
using namespace std;
typedef long long LL;
const int N = 150005;
struct Node {
int left , right , add , mn;
}L[N << 2];
int n , h , b[N] , len , a[N];
void bulid (int step , int l , int r) {
L[step].left = l;
L[step].right = r;
L[step].add = 0;
L[step].mn = 0;
if (l == r) return ;
int m = (l + r) >> 1;
bulid (lson , l , m);
bulid (rson , m + 1 , r);
}
void update (int step , int l , int r , int v);
void push_down (int step) {
int l = L[step].left , r = L[step].right , m = (l + r) >> 1;
if (L[step].add) {
update (lson , l , m , L[step].add);
update (rson , m + 1 , r , L[step].add);
L[step].add = 0;
}
}
void push_up (int step) {
L[step].mn = min (L[lson].mn , L[rson].mn);
}
void update (int step , int l , int r , int v) {
if (L[step].left == l && L[step].right == r) {
L[step].mn += v;
L[step].add += v;
return ;
}
push_down (step);
int m = (L[step].left + L[step].right) >> 1;
if (r <= m) update (lson , l , r , v);
else if (l > m) update (rson , l , r , v);
else {
update (lson , l , m , v);
update (rson , m + 1 , r , v);
}
push_up (step);
}
int main() {
int t;
#ifndef ONLINE_JUDGE
freopen ("input.txt" , "r" , stdin);
// freopen ("output.txt" , "w" , stdout);
#endif
scanf ("%d %d %d" , &n , &len , &h);
for (int i = 0 ; i < len ; i ++)
scanf ("%d" , &b[i]);
sort (b , b + len);
bulid (1 , 0 , len);
for (int i = 0 ; i < n ; i ++) {
scanf ("%d" , &a[i]);
a[i] = lower_bound (b , b + len , h - a[i]) - b;
}
for (int i = 0 ; i < len ; i ++)
update (1 , i , i , -(i + 1));
for (int i = 0 ; i < len - 1 ; i ++)
update (1 , a[i] , len , 1);
int ans = 0;
for (int i = len - 1 ; i < n ; i ++) {
update (1 , a[i] , len , 1);
if (L[1].mn >= 0) ans ++;
update (1 , a[i - len + 1] , len , -1);
}
printf ("%d\n" , ans);
return 0;
}