题解：P11340 [COI 2019] TENIS

LastKismet · 2025-10-25 23:56:44 · 题解

Sol

为什么都在找性质啊，这个不是暴力维护一下就行了吗。

前情提要：模拟赛 T3 放这个一眼秒了然后挂大分。

如果我们把图建出来的话，显然只要满足缩点之后查询的点入度为 0 即可，一个强连通分量中的点显然可以钦定任意一点为该联通分量的赢家。

考虑以第一条链为基准，视其为一棵 DFS 生成树，然后对另外两条链，不难发现有用的其实只有链上相邻两点的连边，把这些新的边视作非树边直接连到第一条链生成的链状生成树上去。后文的“链”无特殊说明均指作为基准的第一条链。

先不考虑修改，考虑一个点所在连通分量缩点后入度为零的充要条件，那么只要这个点与链头在一个 SCC 即可，更一般的，要求链上链头到当前点的每个点（不考虑链头）均满足后缀 \min(low)<rk，low 表示当前点自己和连向的点中在基准链上最靠左的位置，rk 表示这个点自己在链上的位置。

维护这个的话，只需要维护最前面一个后缀 \min(low)\ge rk 的点（不考虑链头）即可，这个点就是最靠前的割边右侧的点（证明参考 tarjan 算法），后文简记该点为割点。假如查询的点在这个割点前面就可行，否则必然不可行。

由于是一条链，可以在线段树上维护区间最小 low，与只考虑当前区间内的点时最靠前的割点编号，更新方式比较显然，可以参考代码：

void change(int k,int v,int x=1,int l=2,int r=n){
    if(k<l)return;
    if(l==r)return dat[x]=v,res[x]=(dat[x]>=l?l:n+1),void();
    int m=l+r>>1;
    if(k<=m)change(k,v,x<<1,l,m);
    else change(k,v,x<<1|1,m+1,r);
    dat[x]=min(dat[x<<1],dat[x<<1|1]);
    res[x]=res[x<<1];
    if(dat[x<<1|1]<res[x])res[x]=res[x<<1|1];
}

上面代码是修改一个点的 low 时顺便更新答案。那么整个序列最靠前的割点位置就是 res[1]（若无赋值为 n+1）。

考虑修改，不难发现，我们每次只会断开相应链上与两个互换点相连的不超过 4 条边，并新连上同样数量的边数，同时总非树边数不超过 2n，那么我们考虑直接维护每个点所有的非树边指向的点编号，断边、连边时直接暴力改即可，然后将有变化的点的 low 信息暴力重新跑一边所有连边更新。

特殊地，如果改的是基准链，那么虽然不用断边或者连边，但是由于 rk 发生了变化，有非树边连向它的所有点也必须更新 low 信息，枚举两条链找连向它们的点即可。

易错点：一定要把所有要更新的点更新完！可能有重边所以不要用 set 存图！！！

所以为什么这种奶龙题赛时会挂挂挂呢。QAQ

Code

const int N=1e5+5,P=4;

int n,q;
int a[N];
int l[P][N],rk[P][N];
int low[N];

int dat[N<<2],res[N<<2];
void change(int k,int v,int x=1,int l=2,int r=n){
    if(k<l)return;
    if(l==r)return dat[x]=v,res[x]=(dat[x]>=l?l:n+1),void();
    int m=l+r>>1;
    if(k<=m)change(k,v,x<<1,l,m);
    else change(k,v,x<<1|1,m+1,r);
    dat[x]=min(dat[x<<1],dat[x<<1|1]);
    res[x]=res[x<<1];
    if(dat[x<<1|1]<res[x])res[x]=res[x<<1|1];
}

multiset<int> g[N];

inline void Main(){
    cin>>n>>q;
    rep(p,1,3){
        rep(i,1,n)cin>>l[p][i],rk[p][l[p][i]]=i;
        if(p==1)rep(i,1,n)low[i]=rk[1][i];
        if(p>1){
            repl(i,1,n){
                int x=l[p][i],y=l[p][i+1];
                chmin(low[x],rk[1][y]);
                g[x].insert(y);
            }
        }
    }
    rep(i,1,n)change(rk[1][i],low[i]);
    rep(i,1,q){
        int op;cin>>op;
        if(op==1){
            int x;cin>>x;
            put(res[1]>rk[1][x]?"DA":"NE");
        }else{
            int p,a,b;cin>>p>>a>>b;
            if(rk[p][a]>rk[p][b])swap(a,b);
            if(p==1){
                swap(l[1][rk[1][a]],l[1][rk[1][b]]);
                swap(rk[1][a],rk[1][b]);
                swap(a,b);
                low[a]=rk[1][a];
                for(auto k:g[a])chmin(low[a],rk[1][k]);
                change(rk[1][a],low[a]);
                low[b]=rk[1][b];
                for(auto k:g[b])chmin(low[b],rk[1][k]);
                change(rk[1][b],low[b]);
                rep(p,2,3){
                    int z;
                    if(rk[p][a]>1){
                        z=l[p][rk[p][a]-1];
                        low[z]=rk[1][z];
                        for(auto k:g[z])chmin(low[z],rk[1][k]);
                        change(rk[1][z],low[z]);
                    }
                    if(rk[p][b]>1){
                        z=l[p][rk[p][b]-1];
                        low[z]=rk[1][z];
                        for(auto k:g[z])chmin(low[z],rk[1][k]);
                        change(rk[1][z],low[z]);
                    }
                }
            }else{
                int z;
                if(rk[p][a]>1){
                    z=l[p][rk[p][a]-1];
                    g[z].erase(g[z].lower_bound(a));
                }
                if(rk[p][a]<n){
                    z=l[p][rk[p][a]+1];
                    g[a].erase(g[a].lower_bound(z));
                }
                if(rk[p][b]>1&&l[p][rk[p][b]-1]!=a){
                    z=l[p][rk[p][b]-1];
                    g[z].erase(g[z].lower_bound(b));
                }
                if(rk[p][b]<n){
                    z=l[p][rk[p][b]+1];
                    g[b].erase(g[b].lower_bound(z));
                }
                swap(l[p][rk[p][a]],l[p][rk[p][b]]);
                swap(rk[p][a],rk[p][b]);
                swap(a,b);
                if(rk[p][a]>1){
                    z=l[p][rk[p][a]-1];
                    g[z].insert(a);
                    low[z]=rk[1][z];
                    for(auto k:g[z])chmin(low[z],rk[1][k]);
                    change(rk[1][z],low[z]);
                }
                if(rk[p][a]<n){
                    z=l[p][rk[p][a]+1];
                    g[a].insert(z);
                }
                if(rk[p][b]>1&&l[p][rk[p][b]-1]!=a){
                    z=l[p][rk[p][b]-1];
                    g[z].insert(b);
                    low[z]=rk[1][z];
                    for(auto k:g[z])chmin(low[z],rk[1][k]);
                    change(rk[1][z],low[z]);
                }
                if(rk[p][b]<n){
                    z=l[p][rk[p][b]+1];
                    g[b].insert(z);
                }
                low[a]=rk[1][a];
                for(auto k:g[a])chmin(low[a],rk[1][k]);
                change(rk[1][a],low[a]);
                low[b]=rk[1][b];
                for(auto k:g[b])chmin(low[b],rk[1][k]);
                change(rk[1][b],low[b]);
            }
        }
    }
}