题解：P12118 [NordicOI 2025] 点对处理 / Dodgeball Diplomacy

· · 题解

P12118

会了 O(q\sqrt n\log n) 后以为过不了就去晚自习了！不过不同的手法还是有巨大差别的。

思路

强制在线。删边分裂是最大的问题，考虑根号重构。

最开始想的是按时间分块，每 B 个操作一块。每进入一块之前重构整个图。重构时，并查集加入部分之前的边，但不加入之前的边中前 B 大的。加入删除时，不修改并查集，这样就算删边也删不到在图中的边。询问时，加入剩下的边，查询，再撤销，需要可撤销并查集。常数有点爆炸，口胡完就下播了。

后来又想到更好的重构方式。重构时，按边从小到大排序加入并查集。加入时，把新边加入一个 set 中，不修改并查集。删除时，要么删 set 中一个元素，要么撤销最后一次并查集加边。当 set 中元素个数 \ge B 时，把边重新排序，重构，至多 \frac{q}{B} 次。

至于处理答案，即把连通块大小排序后两两配对，在并查集操作时修改每个并查集大小的数量。一开始想用权值线段树维护区间的 (val,num)，被卡常了。注意到只有 O(\sqrt n) 种本质不同的 siz，直接维护是哪些数即可。

复杂度 O(q\log n+q(B\log n+\sqrt n\log n)+\frac{q}{B}n\log n)。

code

int n,q;
int t[maxn],id[maxn],pos[maxn],idx,tmp[maxn];
void upd(int p,int w){
    t[p]+=w;
    if(t[p]==w)id[++idx]=p,pos[p]=idx;
    if(t[p]==0)pos[id[idx]]=pos[p],id[pos[p]]=id[idx],idx--;
}
void clr(){
    while(idx)t[id[idx]]=0,idx--;
}
int calc(){
    for(int i=1;i<=idx;i++)tmp[i]=id[i];
    sort(tmp+1,tmp+idx+1);
    int ans=0;
    for(int i=idx,op=0;i;i--)if(t[tmp[i]]&1)ans+=tmp[i]*(!op?1:-1),op^=1;
    return ans;
}
int f[maxn],siz[maxn];
int fd(int x){
    if(f[x]==x)return x;
    return fd(f[x]);
}
int st[maxm],tp;
void merge(int u,int v){
    u=fd(u),v=fd(v);
    if(u==v){st[++tp]=0;return ;}
    if(siz[u]<siz[v])swap(u,v);
    upd(siz[u],-1),upd(siz[v],-1);
    st[++tp]=v;f[v]=u,siz[u]+=siz[v];
    upd(siz[u],1);
}
void del(){
    int v=st[tp],u=f[st[tp]];tp--;
    if(!v)return ;
    upd(siz[u],-1);
    f[v]=v,siz[u]-=siz[v];
    upd(siz[u],1),upd(siz[v],1);
}
tuple<int,int,int> e[maxm],e1[maxm],e2[maxm];int m,m1,m2;
set<tuple<int,int,int>> s;
void init(){
    for(int i=1;i<=n;i++)f[i]=i,siz[i]=1;tp=0;
    clr();upd(1,n);
}
void rebuild(){
    m1=0;for(auto p:s)e1[++m1]=p;
    m2=0;for(int i=1;i<=m;i++)e2[++m2]=e[i];
    s.clear();
    int p=1,q=1;m=0;
    while(p<=m1&&q<=m2){
        if(e1[p]<=e2[q])e[++m]=e1[p++];
        else e[++m]=e2[q++];
    }
    while(p<=m1)e[++m]=e1[p++];
    while(q<=m2)e[++m]=e2[q++];
    init();
    for(int i=1;i<=m;i++)merge(get<1>(e[i]),get<2>(e[i]));
}
void work(){
    n=read();q=read();init();
    while(q--){
        char op=readc();
        if(op=='a'){
            int u=read(),v=read(),w=read();
            s.insert({w,u,v});
        }
        if(op=='r'){
            if(!s.size()||(*--s.end())<=e[m])del(),m--;
            else s.erase(--s.end());
        }
        if(op=='d'){
            if(s.size()>B)rebuild();
            int lst=tp;
            for(auto[w,u,v]:s)merge(u,v);
            printf("%d\n",calc());fflush(stdout);
            while(tp>lst)del();
        }
    }
}