专栏文章

题解：CF500E New Year Domino

ffzs7
CF500E题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miov6oko
此快照首次捕获于
2025/12/03 01:41
3 个月前
此快照最后确认于
2025/12/03 01:41
3 个月前
查看原文
提供一个回滚莫队解法
首先有个显而易见的结论，若 i<ji<j 且 pi+li>pj+ljp_i + l_i > p_j + l_j 那如果两者都在询问区间里，jj 就不用考虑了。
考虑寻找答案的过程，记 pi+li=sip_i + l_i = s_i，设询问区间为 [l,r][l,r] 那么相当于在 [l,r−1][l,r-1] 中找 ss 的最大值 g1g_1，把 g1g_1 到达 rr 的最小代价加到答案中，然后再找 g1g_1 前面的 ss 最大值所在位置 g2g_2，答案加上这个位置的贡献……
观察到只有前缀最大值是对答案有贡献的，考虑将这些前缀最大值所在点加入一个双端队列中，设双端队列末尾为 backback，开头为 frontfront，考虑当前答案区间 [L,R][L,R] 往右扩展一格会发生什么变化，发现只需分两种情况，sback<sR+1s_{back}<s_{R + 1} 时将 R+1R+1 加入双端队列并统计贡献，否则直接忽略。
（代码中用数组模拟双端队列，calccalc 函数用来计算贡献）
CPP
if (s[que[back]]<s[R+1]) que[++back]=R+1,ans+=calc(back);
再考虑向前拓展会发生什么情况，发现可以用类似单调队列的方法，也就是不断把队列前端 sfront<sL−1s_{front}<s_{L-1} 的 frontfront 弹出，最后把 L−1L-1 加入队列前端。
CPP
while (front<=back&&s[que[front]]<s[L-1]) {
    if (front<back)//判有没有可删除贡献
        ans-=calc(front+1);
    front++;
}
que[--front]=L-1;
if (front<back) ans+=calc(front+1);
感觉不可删除两端，所以用回滚莫队维护这一过程。
然后注意到向前扩展需要均摊后时间复杂度才是对的，所以我们回滚的时候若撤销向前扩展的操作，时间复杂度可能出错，所以我们以右端点所在块为第一关键字排序，左端点为第二关键字排序，每次撤销向后扩展的操作即可。
时间复杂度 O(nn)O(n\sqrt n)
给出代码
CPP
#include <bits/stdc++.h>
using namespace std;

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

struct node {
	long long l, r, id;
};

const int k = 450;
long long n, q, cnt, nl, nr, l[200005], r[200005], bl[1000], qwq[200005], ans[200005], que[500005], h, t;
vector<node> query[1000];

bool cmp (node x, node y) {
	return x. l > y. l;
}

int main(void) {
	n = read();
	for (int i = 1; i <= n; i++) qwq[i] = (i - 1) / k + 1, bl[qwq[i]] = bl[qwq[i]] ? bl[qwq[i]] : i;
	for (int i = 1; i <= n; i++) l[i] = read(), r[i] = l[i] + read();
	q = read();
	for (int i = 1; i <= q; i++) {
		nl = read(), nr = read();
		if (qwq[nl] == qwq[nr]) {
			h = 0;
			for (int j = nl; j <= nr; j++) {
				if (!h) que[++h] = j;
				else if (r[j] > r[que[h]]) que[++h] = j, ans[i] += max(l[que[h]] - r[que[h - 1]], 0ll);
			}
		} else query[qwq[nr]]. push_back({nl, nr, i});
	}
	for (int i = 1; i <= qwq[n]; i++) {
		if (query[i]. empty()) continue;
		sort(query[i]. begin(), query[i]. end(), cmp);
		long long p = bl[i], s = 0;
		h = 250000, t = 249999;
		for (auto [ql, qr, id] : query[i]) {
			while (p > ql) {
				p--;
				while (h <= t && r[que[h]] < r[p]) {
					if (h < t) s -= max(0ll, l[que[h + 1]] - r[que[h]]);
					h++;
				}
				que[--h] = p;
				if (h < t) s += max(0ll, l[que[h + 1]] - r[que[h]]);
			}
			long long _t = t, _s = s;
			for (int j = bl[i]; j <= qr; j++) if (r[que[t]] < r[j]) que[++t] = j, s += max(0ll, l[que[t]] - r[que[t - 1]]);
			ans[id] = s + max(0ll, l[qr] - r[que[t]]);
			t = _t, s = _s;
		}
	}
	for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...