题解：P11519 [CCO 2024] Telephone Plans

· · 题解

[CCO 2024] Telephone Plans 题解

[CCO 2024] Telephone Plans 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

启发式合并，启发式分裂，BFS，LCT。

分析

首先有“所有边连接起来会得到森林”和“所有边只会出现一段连续的时间”两个重要条件。

然后对于连边和删边就有如下算法：

两者的均摊复杂度皆为 O(n\log_2{n})。

最后考虑查询。

我们可以考虑记一个目前总共合并过的节点对数 sum，每次连边时，将两个连通块 u,v 的大小相乘并加入 sum，即 sum\gets sum +siz_u\times siz_v。

除此之外再记一个 d_{i} 表示第 i 次操作使节点对数减少的数量，那么在删边时，对于分裂出来的两个连通块 u,v，将他们相乘并记下即可 d_i\gets siz_u\times siz_v。如果操作不是删边，则 d_i\gets 0。

那么第 q 次查询 t 的答案就是 sum-\sum_{i=1}^{q-t}d_i，对 d 做前缀和即可解决。

代码

已略去快读快写。

bool vis[N];
int ALWAYS_ONLINE,n,Q,top;
int idx[N],siz[N],st[N];
ll ans(0),sum(0);
ll del[Qr];
gp_hash_table<int,null_type> g[N];

void dfs(int u,int fa,int new_idx) {
    idx[u]=new_idx;
    for(auto &v:g[u])if(v!=fa)dfs(v,u,new_idx);
}

signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
    I(ALWAYS_ONLINE,n,Q);
    FOR(i,1,n)idx[i]=i,siz[i]=1;
    FOR(q,1,Q) {
        int op;
        ll x,y,t;
        I(op),op<3?I(x,y):I(t),del[q]=del[q-1];
        if(ALWAYS_ONLINE)op<3?x^=ans,y^=ans:t^=ans;
        if(op==1) {
            int u(idx[x]),v(idx[y]);
            if(siz[u]>siz[v])swap(u,v),swap(x,y);
            st[++top]=u,sum+=(ll)siz[u]*siz[v],siz[v]+=siz[u],dfs(x,0,v),g[x].insert(y),g[y].insert(x);
        } else if(op==2) {
            int u(idx[x]),v(idx[y]);
            g[x].erase(y),g[y].erase(x);
            stack<int> sx,sy;
            queue< pair<int,Hit> > qx,qy;
            vis[x]=true,sx.push(x);
            if(!g[x].empty())qx.push({x,g[x].begin()});
            vis[y]=true,sy.push(y);
            if(!g[y].empty())qy.push({y,g[y].begin()});
            while(!qx.empty()&&!qy.empty()) {
                auto Update=[&](stack<int> &s,queue< pair<int,Hit> > &q) {
                    int u(q.front().first),v(0);
                    Hit it(q.front().second);
                    q.pop(),v=*it;
                    if(!vis[v]) {
                        vis[v]=true,s.push(v);
                        if(!g[v].empty())q.push({v,g[v].begin()});
                    }
                    if((++it)!=g[u].end())q.push({u,it});
                };
                Update(sx,qx),Update(sy,qy);
            }
            auto Split=[&](stack<int> &sx,stack<int> &sy) {
                siz[u=st[top--]]=sx.size(),siz[v]-=siz[u],del[q]+=(ll)siz[u]*siz[v];
                while(!sx.empty())idx[sx.top()]=u,vis[sx.top()]=false,sx.pop();
                while(!sy.empty())vis[sy.top()]=false,sy.pop();
            };
            qx.empty()?Split(sx,sy):Split(sy,sx);

        } else O(ans=sum-del[q-t],'\n');
    }
    return 0;
}