跑的还挺快。

Problem

https://ac.nowcoder.com/acm/contest/11256/I

Solution

回滚莫队的特点在于把“删点”变成了“撤销”。也就是变成了“按顺序删按顺序加入的点”。

这么说来其实没有太大的本质区别，只是给“删点”加了特殊条件而已。

但只要这么干了就可以用可撤销并查集了。

听说 std 用的是双向链表，我不会。我想想其实并查集跟我想象的双向链表差别不大的样子。

https://www.cnblogs.com/Parsnip/p/10969989.html

对于左端点处在同一个块里的询问，右端点升序排序。每次将莫队左端点重置在块的最右侧，右端点因为是升序的无需重置。

重置的过程就是撤销。

如果右端点一开始是在块的最右侧的左侧，说明这个询问可以暴力查询。

复杂度反正是 $O(n\sqrt{n})$ 的，似乎也不像莫队了。应该算是另一种根号区间处理问题的方式吧。

最后用可撤销并查集维护一下深度、子树大小就行。说是并查集可撤销其实要撤销的不只是并查集，这一点需要稍微注意一下。

撤销方式就是很裸的往 stack 插入你的修改记录。

顺带一提由于用了可撤销并查集本题时间复杂度上界应该是 $O(n\sqrt{n}\log n + k\log n)$ 的。

本题还有一些无聊且容易让人误解的限制条件。

Code

#include<bits/stdc++.h>
#define MOD (998244353)
using namespace std;
// head
template<typename T>inline void gn(T &x) {
    char ch=getchar(), pl=1; x=0;
    while(!isdigit(ch)) pl=(ch=='-'?-1:1), ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
    x*=pl;
}
typedef long long ll;
const int N=1e5+10, M=N<<2;
struct Query {
    int l, r, k, id;
} qu[N];
int a[N];

// union-find
int fa[N], rk[N], sz[N];
int Find(int x) {
    return fa[x]?Find(fa[x]):x;
}
stack<int> ca, cb, ra, rb, cc;
void Union(int a, int b, bool w) {
    int af=Find(a), bf=Find(b);
    if(af==bf) return;
    if(rk[af]>rk[bf]) swap(af, bf);
    if(w) {
        ca.push(af), cb.push(bf), ra.push(rk[af]), rb.push(rk[bf]);
    }
    sz[bf]+=sz[af];
    fa[af]=bf;
    rk[bf]=max(rk[bf], rk[af]+1);
}

// mo
int n, q;
int Be[N], Ber[N], unit;
int cnt[N];
ll ans[N];
int nans;
bool cmp(const Query &a, const Query &b) {
    return Be[a.l]==Be[b.l]?a.r<b.r:a.l<b.l;
}
void Add(int _x, bool w) {
    int x=a[_x];
    cnt[x]++;
    if(w) cc.push(x);
    if(cnt[x-1]) Union(x, x-1, w);
    if(cnt[x+1]) Union(x, x+1, w);
    nans=max(nans, sz[Find(x)]);
}
void Widr() {
    while(!ca.empty()) {
        rk[ca.top()]=ra.top();
        rk[cb.top()]=rb.top();
        fa[ca.top()]=0;
        sz[cb.top()]-=sz[ca.top()];
        ca.pop(), cb.pop(), ra.pop(), rb.pop();
    }
    while(!cc.empty()) cnt[cc.top()]--, cc.pop();
}

// pre
int ppo[N];

int main() {
    gn(n), gn(q);
    ppo[0]=1;
    for(int i=1; i<N; i++)
        ppo[i]=1ll*ppo[i-1]*(n+1)%MOD;
    int unit = sqrt(n);
    for(int i=1; i<=n; i++) Be[i]=i/unit, Ber[Be[i]]=i;
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
    for(int i=1; i<=q; i++) {
        gn(qu[i].l), gn(qu[i].r), gn(qu[i].k);
        qu[i].id=i;
    }
    sort(qu+1, qu+1+q, cmp);
    int xl, xr;
    int rans;
    int nl, nr;
    for(int i=1; i<=q; i++) {
        nl=qu[i].l, nr=qu[i].r;
        if(Be[nl]!=Be[qu[i-1].l] || i==1) {
            xr=Ber[Be[nl]];
            memset(fa, 0, sizeof(fa));
            memset(rk, 0, sizeof(rk));
            for(int i=1; i<=n; i++) sz[i]=1, cnt[i]=0;
            nans=1;
        }
        if(nr<Ber[Be[nl]]) {
            rans=nans;
            xl=nl;
            xr=nl-1;
            while(xr<nr) Add(++xr, true);
            for(int j=0; j<qu[i].k; j++) {
                ans[qu[i].id]+=1ll*nans*ppo[j]%MOD;
                if(j<qu[i].k-1) Add(--xl, true), Add(++xr, true);
            }
            nans=rans;
            Widr();
            xr=Ber[Be[nl]];
            continue;
        }
        xl=Ber[Be[nl]]+1;
        while(xr<nr) Add(++xr, false);
        rans=nans;
        while(xl>nl) Add(--xl, true);
        for(int j=0; j<qu[i].k; j++) {
            ans[qu[i].id]+=1ll*nans*ppo[j]%MOD;
            if(j<qu[i].k-1) Add(--xl, true), Add(++xr, true);
        }
        nans=rans;
        xr=nr;
        Widr();
    }
    for(int i=1; i<=q; i++)
        printf("%lld\n", ans[i]%MOD);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/niuke2021-i.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆