归档 221009 | 做题记录

B. 萌萌哒

很容易想到对于形如 \([l_1, r_1]\) 和 \([l_2, r_2]\)，只需让两个区间内每个数两两对应相等。由相等关系易联想到并查集。

如果暴力合并整个区间的话，复杂度是 \(\mathcal O(n^2\alpha)\) 的，考虑优化。

然而并没有想到怎么优化（哭哭

瞅了一眼题解，可以用倍增？？？过于玄学，下次再做吧（

D. Wilcze doły

因为都是正数，所以删最多，也就是说要删就得一次性删 \(d\) 个。

不难想到对于一个区间，肯定选择删掉区间内总和最大的连续 \(d\) 个数。

枚举右端点 \(i\)，单调队列维护左右端点间总和最大的连续 \(d\) 个数。

问题来了，左端点怎么找？这是这道题的关键。需要想明白，以 \(i + 1\) 为右端点的区间的左端点 不可能比 以 \(i\) 为右端点的区间的左端点 更靠左。也就是说，左端点具有单调性。

假设当前左端点为 \(l\)，则当 \([l,i]\) 的总和减去最大的 \(d\) 个数的和后仍然大于 \(p\)，就可以将 \(l\) 向后移动了。

namespace XSC062 {
using namespace fastIO;
const int maxn = 2e6 + 5;
int n, p, d, l, h, t, ans;
int a[maxn], s[maxn], q[maxn];
inline int max(int x, int y) {
	return x > y ? x : y; 
}
int main() {
	read(n), read(p), read(d);
	l = 1;
	q[h = t = 1] = d;
	for (int i = 1; i <= n; ++i) {
		read(a[i]);
		a[i] += a[i - 1];
		if (i >= d)
			s[i] = a[i] - a[i - d];
		if (i > d) {
			while (h <= t && q[h] - d + 1 < l)
				++h;
			while (h < t && a[i] - a[l - 1] - s[q[h]] > p) {
				while (h <= t && a[i] - a[l - 1] - s[q[h]] > p)
					++l;
				while (h <= t && q[h] - d + 1 < l)
					++h;
			}
			ans = max(ans, i - l + 1);
			while (h <= t && s[i] >= s[q[t]])
				--t;
			q[++t] = i;
		}
	}
	print(ans);
	return 0;
}
} // namespace XSC062