题解：P11519 [CCO2024] Telephone Plans

缪凌锴_Mathew · 2025-01-07 16:26:05 · 题解

非 LCT 做法。

解法

有一个非常重要的隐藏信息：“每条电话线只能在一段时间内使用”，这意味着每条边只会被加入一次。

对于一组点对 (x,y)，其连通的时间必为一个连续段 [l_{x,y},r_{x,y}]。

查询 t，当前时间为 s，即计算 \displaystyle\sum_{(x,y)}\Big[[l_{x,y},r_{x,y}]\cap(s-t,s]\ne\varnothing\Big]（外层大中括号为艾弗森括号）

我们分成两部分：

• 记 $del_i$ 为满足时刻 $i-1$ 连通且时刻 $i$ 不连通的点对 $(x,y)$ 数量。（显然 $i$ 为删边操作才有值）

询问答案即为 cur-\sum\limits_{i=1}^{s-t}del_i。

对于第一部分，考虑启发式合并。

连边 (u,v) 时，对 cur 贡献 siz_u\times siz_v，其中 siz_x 表示当前 x 所处连通块大小。

对于第二部分，考虑启发式分裂。

删边 (u,v) 时，同时 bfs u,v 所处连通块，bfs 完一个连通块所有点就退出，del=siz_u\times siz_v。

复杂度分析

注意到两个操作复杂度都为 O(\min\{siz_u,siz_v\})。

• 连边操作：若没有删边，总复杂度应为 O(n\log n)（启发式合并），有删边只会使复杂度更小。

• 删边操作：若没有连边，总复杂度应为 O(n\log n)（启发式分裂），有连边只会使复杂度更小。

故总复杂度 O(n\log n+q)。

实现细节

• 强制在线，不能预先知道树的形态，故用 set 作邻接表存树。（我用了 unordered_set）

• 删边的 bfs 特别注意：

  用两个队列，每次扩展一个点所有出边是错误的，这样复杂度并不是 O(\min\{siz_u,siz_v\})。

  需要一条一条边扩展，但是这个 set 邻接表非常麻烦，要把边对应的迭代器也扔进队列。

• 扩展时注意父子关系，不要父亲扩展儿子、儿子扩展回父亲。

• 答案为 long long 级别，强制在线，输入也要开 long long。

Code

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=5e5+10;
const int MAXM=1.5e6+10;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,m,typ;
long long ans=0,cur=0;
long long del[MAXM];
int t;//当前时间戳
int tim[MAXN];//这个数组充当 bool vis[MAXN] 的作用，记录上次访问时间戳，这样就不用清空
#include<unordered_set>
struct splitmix64{
    inline int operator ()(int x)const{
        x^=x<<13;
        x^=x>>11;
        x^=x<<7;
        return x;
    }
};
unordered_set <int,splitmix64> tr[MAXN];
inline void add_edge(int x,int y){
    tr[x].insert(y);
    tr[y].insert(x);
}
inline void del_edge(int x,int y){
    tr[x].erase(y);
    tr[y].erase(x);
}
int siz[MAXN],col[MAXN];
basic_string <int> wst;//连通块编号(col)的垃圾回收
void flood_fill(int x,int rt){
    tim[x]=t;
    siz[rt]++;
    col[x]=rt;
    for(int to:tr[x])
    {
        if(tim[to]==t){
            continue;
        }
        flood_fill(to,rt);
    }
}
inline long long link(int x,int y){
    add_edge(x,y);
    if(siz[col[x]]<siz[col[y]]){
        swap(x,y);
    }
    long long res=1ll*siz[col[x]]*siz[col[y]];
    siz[col[y]]=0;
    wst.push_back(col[y]);
    tim[x]=t;
    flood_fill(y,col[x]);
    return res;
}
#define node tuple<int,unordered_set <int,splitmix64>::iterator>
inline long long cut(int x,int y){
    del_edge(x,y);
    queue <node> p,q;
    if(!tr[x].empty()){
        p.push(node(x,tr[x].begin()));
    }
    if(!tr[y].empty()){
        q.push(node(y,tr[y].begin()));
    }
    while(!p.empty()&&!q.empty())
    {
        #define work(Q){\
            auto [x,it]=Q.front();\
            tim[x]=-t;/*这里的-t是弹出队列的标记*/\
            Q.pop();\
            if(tr[*it].size()>1){\
                auto to=tr[*it].begin();\
                if(*to==x){\
                    to++;\
                }\
                Q.push(node(*it,to));\
            }\
            it++;\
            if(it!=tr[x].end()&&tim[*it]==-t){/*若*it已弹出队列，则*it为x的父亲*/\
                it++;\
            }\
            if(it!=tr[x].end()){\
                Q.push(node(x,it));\
            }\
        }
        work(p);
        work(q);
    }
    if(p.empty()){
        swap(x,y);
    }
    int rt=wst.back();
    wst.pop_back();
    flood_fill(y,rt);
    siz[col[x]]-=siz[col[y]];
    return 1ll*siz[col[x]]*siz[col[y]];
}
inline void solve(){
    scanf("%d",&typ);
    scanf("%d%d",&n,&m);
    iota(col+1,col+1+n,1);
    fill(siz+1,siz+1+n,1);
    for(t=1;t<=m;t++)
    {
        del[t]=del[t-1];
        int opt;
        scanf("%d",&opt);
        if(opt^3){
            long long x,y;
            scanf("%lld%lld",&x,&y);
            if(typ){
                x^=ans;
                y^=ans;
            }
            if(opt==1){
                cur+=link(x,y);
            }
            else{
                del[t]+=cut(x,y);
            }
        }
        else{
            long long x;
            scanf("%lld",&x);
            if(typ){
                x^=ans;
            }
            ans=cur-del[t-x];
            printf("%lld\n",ans);
        }
    }
}
signed main(){
    #ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
    #endif
    solve();
    return 0;
}