CF765F 题解

· · 题解

为什么大家都不写莫队！

题面

给定长度为 n 的序列 a，m 次询问一个 [l, r]，求 \min\limits_{i, j \in [l, r]}{|a_i - a_j|}。

题解

考虑莫队，最暴力的朴素莫队必然是用 set 维护元素集合和相邻两个数的差的集合，复杂度 O(n \sqrt m \log n)，大概死的比较惨烈。

考虑到如果每次只插入一个数，我们只需要求出这个数的前驱和后继即可快速更新答案，于是不难想到使用回滚莫队和链表。

我们考虑把只加入的回滚莫队和只删除的回滚莫队硬缝一下，并将计算答案的过程分成两步。

第一步，首先对于一个询问 [l, r]，不妨设 l \in [bl, br]，r \in (br, n]，其中 bl, br 是这一块的边界。如果我们只求 (br, r] 的答案是非常容易的，先搞一个维护 (br, n] 的链表，枚举下标从大到小全删掉，再倒着撤销即可。

现在如果我们拿到了 (br, r] 的链表和对应的答案，再顺着往里面插入 [l, br] 就可以求出最终的答案了。(br, r] 的答案我们用上面的过程已经求出来了，我们只需要拿到一个链表，而且可以通过撤销到 [l, r] 的状态。但是如果我们用刚刚的那个链表，会发现各种撤销的顺序直接揉在一次，根本做不了。

所以考虑第二步，再拿一个新的链表，初始维护 [bl, n]，然后还是先删除再慢慢撤销，撤回到 [bl, r] 的时候，我们顺着删掉 [bl, br]，这样就得到了 (br, r] 的链表了，再撤回到 l 并同时统计答案我们就做完了（当然记得最后再撤回到 bl，不然做不了剩下的询问）。

另外如果 r 也在块内，那第一步就跟它没有关系，第二步的时候删到 r 就停下开始撤销就行。

复杂度与正常的回滚莫队没有任何差异，为 O(n\sqrt m)，由于莫队常数偏小，所以跑得很快，甚至能和 O(n \log^2 n) 拼一拼。

代码中只定义了一个链表，并且重复利用了一下，先做了第二步，再做第一步。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
const int N = 100005, M = 300005, B = 190, C = N / B + 10;
int n, m, a[N], bel[N];
std::pair<int, int> pr[N];
int hh[N];
struct List
{
    int pre[N], nxt[N]; 
    inline void init(void)
    {
        nxt[0] = 1, pre[n + 1] = n;
        for(int i = 1;i <= n;++i)
            pre[i] = i - 1, nxt[i] = i + 1;
        return;
    }
    inline void erase(int k)
    {
        nxt[pre[k]] = nxt[k], pre[nxt[k]] = pre[k];
        return;
    }
    inline int back(int k)
    {
        nxt[pre[k]] = pre[nxt[k]] = k;
        int res = 0x3f3f3f3f;
        if(pre[k] != 0)
            res = std::min(res, hh[k] - hh[pre[k]]);
        if(nxt[k] != n + 1)
            res = std::min(res, hh[nxt[k]] - hh[k]);
        return res;
    }
} L;
int ans[M];
struct node
{
    int l, r, id;
    inline bool operator<(node b) const
    {
        return r < b.r;
    }
};
int big[N];
std::vector<node> vec[C];
int main(void)
{
    scanf("%d", &n);
    for(int i = 1;i <= n;++i)
        scanf("%d", &pr[i].first), pr[i].second = i;
    std::sort(pr + 1, pr + 1 + n);
    for(int i = 1;i <= n;++i)
        a[pr[i].second] = i, hh[i] = pr[i].first, bel[i] = (i - 1) / B + 1;
    scanf("%d", &m);
    for(int i = 1, l, r;i <= m;++i)
    {
        scanf("%d%d", &l, &r);
        vec[bel[l]].push_back({l, r, i});
    }
    memset(ans, 0x3f, sizeof(ans));
    L.init();
    for(int b = 1;b <= bel[n];++b)
    {
        std::sort(vec[b].begin(), vec[b].end());
        int bl = (b - 1) * B + 1, br = std::min(b * B, n);
        for(int i = n;i >= bl;--i)
            L.erase(a[i]);
        int pt = bl - 1;
        for(const node &x : vec[b])
        {
            while(pt < x.r)
                L.back(a[++pt]);
            int k = std::min(x.r, br);
            for(int i = bl;i <= k;++i)
                L.erase(a[i]);
            for(int i = k;i >= x.l;--i)
                ans[x.id] = std::min(ans[x.id], L.back(a[i]));
            for(int i = x.l - 1;i >= bl;--i)
                L.back(a[i]);
        }
        while(pt < n)
            L.back(a[++pt]);
        for(int i = bl;i <= br;++i)
            L.erase(a[i]);
        for(int i = n;i > br;--i)
            L.erase(a[i]);
        big[br] = 0x3f3f3f3f;
        for(int i = br + 1;i <= n;++i)
            big[i] = std::min(big[i - 1], L.back(a[i]));
        for(const node &x : vec[b])
            if(x.r > br)
                ans[x.id] = std::min(ans[x.id], big[x.r]);
    }
    for(int i = 1;i <= m;++i)
        printf("%d\n", ans[i]);
    return 0;
}