题解[P5064 等这场战争结束之后]

Y_B_X · 2022-08-17 21:33:27 · 题解

原题链接

题意：
给定一张无向图，点有点权，需支持：
加一条连接 x,y 的边；
回到某个历史版本；
询问 x 所在连通块中第 k 小的点权。

提供一种时间复杂度 O\left(\dfrac{nm}{w}\right)，空间 O(n+m) 的做法。

先将点权离散化，并让点权相同的点对应不同的离散化后的权值。
这可以让所有点唯一对应不同的权值。
然后把所有点的编号换成其权值，就只需查询连通块中第 k 小的编号。

考虑对每个连通块开一个 \text{bitset}（需手写），单次查询便可以跳整块与散块做到 O\left(\dfrac{n}{w}+w\right)。

可用启发式合并并查集（按子树大小）处理连通块，\text{bitset} 只开在连通块根节点上。

连边可以直接两个 \text{bitset} 或在一起，小的或上大的，单次 O\left(\dfrac{n}{w}\right)。

而对于加边与回退，可以 \text{dfs} 操作树，便只需处理操作树上的回退。

由于加边前子树小的 \text{bitset} 对后续连边无用，可以保留，回退直接将其减掉即可。

这样时间复杂度是 O\left(\dfrac{nm}{w}\right)，空间与时间相同，很不优秀。

但其实在联通块点数较小时没必要浪费一个 \text{bitset} 的空间。

在连通块点数 <\dfrac{n}{w} 时只需维护一个链表，

这样最多开 w 个 \text{bitset}，空间能做到 w\times \dfrac{n}{w}，也就是线性。

再细讲一下合并与撤回。

对于链表和链表的合并，直接让两边首尾相连。
为了撤回一并记录点数大小，因此只需把后几个分开便能撤回。
每个点时时只在一个链表上，空间线性。
这里合并不需要保证有序，查询时拎出来所有点后 \operatorname{nth\ element} 也能做到 O\left(\dfrac{n}{w}\right)。
对于链表与 \text{bitset} 的合并，有链表的子树一定更小，直接遍历链表插入 \text{bitset}。
而合并后链表将不被访问，撤回时再次遍历链表修改 \text{bitset} 每一位。
对于 \text{bitset} 与 \text{bitset} 的合并，与之前一样，
而点数小的 \text{bitset} 仍能保留，且空间使用不会增加。

注意 \operatorname{nth\ element} 带的常数有点大，可让链表最多维护 \dfrac{n}{2w} 个点。

总的时间复杂度就是 O\left(\dfrac{nm}{w}\right)，空间 O(n+m) 。

无需卡常，无需卡空间，畅你所写！

\texttt{Code:}

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int W=64;
const int _W=63;
const int t=6;
const int N=1e5+10;
int n,m,x,y,xx,nn,tot,qq;
int btot,bbtot,lim,tn,ptot;
char opt,ch;
struct bitset{
    ull b[N/W+1];int i,res,l;ull j;
    inline void reset(){memset(b,0,sizeof(b));}
    inline void add(int i){b[i>>t]|=1ull<<(i&(_W));}
    inline void del(int i){b[i>>t]^=1ull<<(i&(_W));}
    inline void operator |=(const bitset &a){
        for(i=0;i!=tn;++i)b[i]|=a.b[i];
    }
    inline void operator ^=(const bitset &a){
        for(i=0;i!=tn;++i)b[i]^=a.b[i];
    }
    inline void inquiry(int k){
        for(i=0;i!=tn;++i){
            l=__builtin_popcountll(b[i]);
            if(l<k)k-=l;else break;
        }
        j=b[i];
        while(--k)j^=(1ull<<__builtin_ctzll(j));
        res=i*W+__builtin_ctzll(j);
    }
}b[101];
int pre[N],suf[N],sz[N],id[N],f[N];
int a[N],_[N],__[N],cnt[N],res[N];
int bin[N],btp,tmp[N],idx;
inline int getf(int x){
    while(x!=f[x])x=f[x];return x;
}
int qx[N],qy[N];bool cvr_id[N];
inline void merge(int x,int y){
    ++ptot;idx=id[x];cvr_id[ptot]=0;
    if(!idx&&sz[x]>lim){
        idx=id[x]=btp?bin[btp--]:++btot;b[idx].add(x);
        xx=x;while(pre[xx])b[idx].add(xx=pre[xx]);
        xx=x;while(suf[xx])b[idx].add(xx=suf[xx]);
        cvr_id[ptot]=1;
    }
    if(id[y])b[idx]|=b[id[y]];
    else {
        if(idx){
            b[idx].add(y);
            xx=y;while(pre[xx])b[idx].add(xx=pre[xx]);
            xx=y;while(suf[xx])b[idx].add(xx=suf[xx]);
        }
        else {
            while(suf[x])x=suf[x];
            while(pre[y])y=pre[y];
            pre[suf[x]=y]=x;
        }
    }
}
inline void draw_back(int x,int y){
    idx=id[x];
    if(id[y])b[idx]^=b[id[y]];
    else {
        if(idx){
            b[idx].del(y);
            xx=y;while(pre[xx])b[idx].del(xx=pre[xx]);
            xx=y;while(suf[xx])b[idx].del(xx=suf[xx]);
        }
        else {
            while(suf[x])x=suf[x];
            xx=sz[y];while(--xx)x=pre[x];
            suf[pre[x]]=0;pre[x]=0;
        }
    }
}
int to[N],nextn[N],h[N],edg;
inline void add_edge(int x,int y){
    to[++edg]=y,nextn[edg]=h[x],h[x]=edg;
}
int nextnq[N],hq[N],xq[N],kk[N],ii[N],edgq;
inline void addq(int x,int xx,int k,int i){
    nextnq[++edgq]=hq[x],hq[x]=edgq;
    xq[edgq]=xx;kk[edgq]=k,ii[edgq]=i;
}
inline void inquiry(int x,int k,int i){
    if(sz[x]<k)res[i]=-1;
    else {
        if(id[x]){
            b[id[x]].inquiry(k);
            res[i]=b[id[x]].res;
        }
        else {
            tmp[nn=1]=x;
            xx=x;while(suf[xx])tmp[++nn]=xx=suf[xx];
            xx=x;while(pre[xx])tmp[++nn]=xx=pre[xx];
            nth_element(tmp+1,tmp+k,tmp+nn+1);
            res[i]=tmp[k];
        }
    }
}
void dfs(int x){
    int i,y,fx,fy;
    fx=getf(qx[x]),fy=getf(qy[x]);
    if(fx!=fy){
        if(sz[fx]<sz[fy])xx=fx,fx=fy,fy=xx;
        sz[fx]+=sz[fy];f[fy]=fx;merge(fx,fy);
    }
    for(i=hq[x];i;i=nextnq[i])
        inquiry(getf(xq[i]),kk[i],ii[i]);
    for(i=h[x];i;i=nextn[i])dfs(to[i]);
    if(fx!=fy){
        sz[fx]-=sz[fy];f[fy]=fy;
        if(cvr_id[ptot--]){
            b[id[fx]].reset();
            bin[++btp]=id[fx];
            id[fx]=0;
        }
        else draw_back(fx,fy);
    }
}
inline void read(int &x){
    x=0;ch=getchar();while(ch<48)ch=getchar();
    while(ch>47)x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
inline void read(char &x){
    x=0;ch=getchar();while(ch<48)ch=getchar();
    x=ch^48,ch=getchar();
}
void write(int x){
    if(x>9)write(x/10);putchar(48|(x%10));
}
main(){
    read(n),read(m);register int i,j;
    lim=n/W/2,tn=n/W+1;
    for(i=1;i<=n;++i)read(a[i]),_[i]=a[i];
    for(i=1;i<=n;++i)sz[i]=1,f[i]=i;
    sort(_+1,_+n+1);nn=unique(_+1,_+n+1)-_-1;
    for(i=1;i<=n;++i)
        ++cnt[a[i]=lower_bound(_+1,_+nn+1,a[i])-_];
    nn=0;
    for(i=1;j=cnt[i],i<=n;++i)
        while(j)--j,__[++nn]=_[i];
    for(i=1;i<=n;++i)cnt[i]+=cnt[i-1];
    for(i=1;i<=n;++i)a[i]=cnt[a[i]]--;
    id[0]=j=tot=1;
    for(i=1;i<=m;++i){
        read(opt),read(x);
        if(opt==1){
            ++tot;add_edge(j,tot);j=tot;
            read(y);qx[j]=a[x],qy[j]=a[y];
        }
        if(opt==2)j=id[x];
        if(opt==3){
            read(y);++qq;
            addq(j,a[x],y,qq);
        }
        id[i]=j;
    }
    for(i=0;i<=m;++i)id[i]=0;
    dfs(1);
    for(i=1;i<=qq;++i){
        res[i]<0?puts("-1"):
        (write(__[res[i]]),putchar('\n'));
    }
}