CF338E Optimize!

CF338E Optimize!

任意匹配，考虑将 $B$ 排序，$B$ 中最大的与 $A$ 中最小的匹配，$B$ 中次大的与 $A$ 中次小的匹配，依次类推。

若满足条件，等价于 $B$ 中最大的至少可以与 $A$ 中 $len$ 个可以匹配，$B$ 中次大的至少可以与 $A$ 中 $len-1$ 个匹配，依次类推。

考虑线段树套扫描线维护，加删数时维护区间加减一，全局询问最小值。

时间复杂度 $\mathcal{O}(n\log n)$。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define ha putchar(' ')
#define he putchar('\n')

inline int read() {
    
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
    
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x * f;
}

inline void write(int x) {
    
	if (x < 0) {
    
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + 48);
}

const int _ = 2e5 + 10;

int n, len, h, a[_], b[_], tr[_ << 2], tag[_ << 2];

void pushdown(int o)
{
    
	tr[o << 1] += tag[o];
	tr[o << 1 | 1] += tag[o];
	tag[o << 1] += tag[o];
	tag[o << 1 | 1] += tag[o];
	tag[o] = 0;
}

void upd(int o, int l, int r, int L, int R, int v)
{
    
	if(L <= l && r <= R)
	{
    
		tr[o] += v, tag[o] += v;
		return;
	}
	pushdown(o);
	int mid = (l + r) >> 1;
	if(L <= mid) upd(o << 1, l, mid, L, R, v);
	if(R > mid) upd(o << 1 | 1, mid + 1, r, L, R, v);
	tr[o] = min(tr[o << 1], tr[o << 1 | 1]);
}

signed main() {
    
	n = read(), len = read(), h = read();
	for (int i = 1; i <= len; ++i) b[i] = read();
	sort(b + 1, b + len + 1);
	for (int i = 1; i <= n; ++i) {
    
		a[i] = read();
		a[i] = lower_bound(b + 1, b + len + 1, h - a[i]) - b;
	}
	for (int i = 1; i <= len; i++) upd(1, 1, len, i, i, -i);
	for (int i = 1; i < len; i++) upd(1, 1, len, a[i], len, 1);
	int ans = 0;
	for (int i = len; i <= n; i++) {
    
		upd(1, 1, len, a[i], len, 1);
		if (tr[1] >= 0) ans++;
		upd(1, 1, len, a[i - len + 1], len, -1);
	}
	write(ans), he;
	return 0;
}