题目大意

给出一个长度为 n的数列 {ai} 和一个长度为 m 的数列 {bi} ，求 {ai} 有多少个长度为 m 的连续子数列能与 {bi} 匹配。
两个数列可以匹配，当且仅当存在一种方案，使两个数列中的数可以在重排后两两配对，两个数可以配对当且仅当它们的和不小于 h 。

输入格式

n,m,h
然后b1..bm
然后a1..an

输出格式

一个整数表示有多少个位置能匹配。

样例输入

5 2 10
5 3
1 8 5 5 7

样例输出

2

解题报告

ai + bi >= h
ai >= h – bi

于是我们把b’i = h – bi

然后从小到大排序b’

对于每个ai求出他放到哪些地方合法（ai >= b’i）

显然是一个前缀

用a去覆盖b，对b的每个位置维护他后面能放几个数，求出需要多少个数字，然后看看每一位是不是可以的。

线段树区间加，区间求最小值。

Orz Orz Orz Orz Orz

我的代码

#include <cstdio>
#include <algorithm>
using namespace std;
int tot, a[150005], b[150005], n, m, h, ans;
inline int getint() {
    register int r = 0; register bool b = true; register char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') b = false; c = getchar(); }
    while (c >= '0' && c <= '9') { r = (r<<1)+(r<<3) + c - '0'; c = getchar(); }
    return b ? r : -r;
}
struct Node {
    int val, tag;
    Node *lc, *rc;
    void add(int x) {
        val += x;
        tag += x;
    }
} tr[300005], *rt;
Node *build(int l, int r) {
    Node *ret = tr + (tot++);
    if (l == r) {
        ret->val = l - m - 1;
    }
    else {
        int mid = (l + r) >> 1;
        ret->lc = build(l, mid);
        ret->rc = build(mid + 1, r);
        ret->val = min(ret->lc->val, ret->rc->val);
    }
    return ret;
}
void change(Node *x, int l, int r, int ll, int rr, int val) {
    if (ll <= l && r <= rr) x->add(val);
    else {
        x->lc->add(x->tag);
        x->rc->add(x->tag);
        x->tag = 0;
        int mid = (l + r) >> 1;
        if (ll <= mid) change(x->lc, l, mid, ll, rr, val);
        if (rr > mid) change(x->rc, mid + 1, r, ll, rr, val);
        x->val = min(x->lc->val, x->rc->val);
    }
}
int main() {
    n = getint(); m = getint(); h = getint();
    for (int i = 1; i <= m; ++i) b[i] = h - getint();
    sort(b + 1, b + m + 1);
    for (int i = 1; i <= n; ++i) a[i] = upper_bound(b + 1, b + m + 1, getint()) - b - 1;
    rt = build(1, m);
    for (int i = 1; i < m; ++i)
        if (a[i] > 0) change(rt, 1, m, 1, a[i], 1);
    for (int i = 1, j = m; j <= n; ++i, ++j) {
        if (a[j] > 0) change(rt, 1, m, 1, a[j], 1);
        if (rt->val >= 0) ++ans;
        if (a[i] > 0) change(rt, 1, m, 1, a[i], -1);
    }
    printf("%d\n", ans);
}