题解：CF500E New Year Domino

· · 题解

提供一个回滚莫队解法

首先有个显而易见的结论，若 i<j 且 p_i + l_i > p_j + l_j 那如果两者都在询问区间里，j 就不用考虑了。

考虑寻找答案的过程，记 p_i + l_i = s_i，设询问区间为 [l,r] 那么相当于在 [l,r-1] 中找 s 的最大值 g_1，把 g_1 到达 r 的最小代价加到答案中，然后再找 g_1 前面的 s 最大值所在位置 g_2，答案加上这个位置的贡献……

观察到只有前缀最大值是对答案有贡献的，考虑将这些前缀最大值所在点加入一个双端队列中，设双端队列末尾为 back，开头为 front，考虑当前答案区间 [L,R] 往右扩展一格会发生什么变化，发现只需分两种情况，s_{back}<s_{R + 1} 时将 R+1 加入双端队列并统计贡献，否则直接忽略。

（代码中用数组模拟双端队列，calc 函数用来计算贡献）

if (s[que[back]]<s[R+1]) que[++back]=R+1,ans+=calc(back);

再考虑向前拓展会发生什么情况，发现可以用类似单调队列的方法，也就是不断把队列前端 s_{front}<s_{L-1} 的 front 弹出，最后把 L-1 加入队列前端。

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(n\sqrt n)

给出代码

#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;
}