题目大意
给出一个长度为 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); }