dsu：P3279 [SCOI2013] 密码

· · 题解

马拉车是什么？我不知道啊？（天真）

来个纯粹并查集做法。

考虑这个玩意其实告诉了我们什么。

有两个区间对称位置相同，有两个点一定不同。

区间翻转一下拼在后面，然后我们强行令翻转前后对应位置相同，于是第一个要做的东西变成两个区间顺序比对依次相同。

萌萌哒 trick ST 表维护并查集即可。

于是我们就把一定相同的给合并了，剩下的是一定不同的边，注意到只有 O(n) 条。

我们把最前面的没填上字母且未染色的给贪心填上目前最优的字母，然后遍历所有互斥边给染色，整个连通块全部染色，然后直接按顺序做即可。非常暴力但是单次复杂度 O(n)。

找点可以用白雪皑皑 trick 并查集维护后继快速完成。

所有字母都来一次，算上前面 ST 表的复杂度，总体时间复杂度 O(n\log n+cn)，其中 c=26 是字符集大小。

并查集不能一遍写对的话调起来和吃史没有本质差别。

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int fa[25][200005];
int find(int op,int x){
    return fa[op][x]==x?x:fa[op][x]=find(op,fa[op][x]);
}
vector<int>ve[100005];
int n,m;
int rev(int x){
    return n-x+1;
}
int nxt2[100005];
int find2(int x){
    return nxt2[x]==x?x:nxt2[x]=find2(nxt2[x]);
}
int vis[100005],op;
int nxt[100005];
int find(int x){
    if(vis[x]!=op)nxt[x]=nxt2[x],vis[x]=op;
    return nxt[x]==x?x:nxt[x]=find(nxt[x]);
}
int ans[100005];
vector<int>c[100005];
signed main(){
    cin>>m;
    n=2*m;
    for(int i=0;i<=20;i++)
    for(int j=1;j<=n;j++)
    fa[i][j]=j;
    for(int i=m+1,j=m;i<=n;i++,j--)
    fa[0][i]=j;
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        x--;
        ve[i-x/2-1].push_back(i+x/2+1);
        ve[i+x/2+1].push_back(i-x/2-1);
        if(!x)continue;
        int l1,r1,l2,r2;
        l1=i-x/2;
        r1=i-1;
        l2=rev(i+x/2);
        r2=rev(i+1);
        int siz=r1-l1+1;
        for(int i=20;i>=0;i--)
        if((1<<i)&siz){
            fa[i][find(i,l1)]=find(i,l2);
            l1+=1<<i;
            l2+=1<<i;
        }
    }
    for(int i=1;i<m;i++){
        int x;
        cin>>x;
        ve[i-x/2].push_back(i+x/2+1);
        ve[i+x/2+1].push_back(i-x/2);
        if(!x)continue;
        int l1,r1,l2,r2;
        l1=i-x/2+1;
        r1=i;
        l2=rev(i+x/2);
        r2=rev(i+1);
        int siz=r1-l1+1;
        for(int i=20;i>=0;i--)
        if((1<<i)&siz){
            fa[i][find(i,l1)]=find(i,l2);
            l1+=1<<i;
            l2+=1<<i;
        }
    }
    for(int i=20;i;i--){
        for(int j=1;j+(1<<i)-1<=n;j++)
        fa[i-1][find(i-1,j)]=find(i-1,find(i,j)),
        fa[i-1][find(i-1,j+(1<<(i-1)))]=find(i-1,find(i,find(i,j)+(1<<(i-1))));
    }
    n=m;
    for(int i=1;i<=n;i++)
    nxt2[i]=i,c[find(0,i)].push_back(i);
    nxt2[n+1]=n+1;
    for(int i=1;i<=n;i++){
        if(ans[i]){
            cout<<(char)(ans[i]+'a'-1);
            continue;
        }
        op++;
        int j=i;
        while(j<=n){
            int flc=find(0,j);
            for(int k:c[flc]){
                nxt2[find2(k)]=find2(k+1);
                nxt[find(k)]=find(k+1);
                ans[k]=op;
                for(int qwq:ve[k]){
                    if(find(qwq)==qwq)
                    for(int kk:c[find(0,qwq)])
                    nxt[find(kk)]=find(kk+1);
                }
            }
            j=find(j);
        }
        cout<<(char)(ans[i]+'a'-1);
    }
    return 0;
}
// 这个房间被打扫的一尘不染呢。
// 一定是维持着十年前的样子吧。

// 那又如何？

// 我也依然把被你们杀死的父亲的房间维持着原来的样子。

// 给这一切书上中止符吧，古拉纳特大人。
// 还是说，你想要双方继续流血和牺牲，继续让谁为此而悲痛欲绝呢？

// 我们的语言是共通的。
// 请务必给我们一个交谈的机会。

// ……带他们去客房。
// 让我考虑一下。

// …………

// 硫古纳大人，父亲是什么？
// 谁知道呢。

讲一个其他更快的写法。

首先你注意到这个东西把并查集建出来合并完以后，得到了若干互斥边，然后根据字典序是从前向后确定的。

我们直接把互斥边对于连通块的代表元建起来，然后依旧是顺序确定，每次确定的时候设置为所有相邻确定数字的 mex 即可。

这个玩意显然可以更快的维护，不用现在这么蠢的对每一个字符都扫一遍，查询 mex 可以用 bitset 或者 set，瓶颈反正是 ST 表复杂度 O(n\log n)。

看完这段你就可以去写 AT_abc349_g 了。过了。

维护 mex 是不是也可以白雪皑皑，用并查集做来着。但我 perm 这么写挂飞了，饿啊。