4246
myee
2021-10-31 18:06:18
### 前言
可能大多数人看到这题就一眼动态图连通性秒了。
但是我发现自己不会敲动态图连通性……
于是，提供一种离线做法。
什么，LCT？
LCT 多难打，放一个**更加暴力而简约**的离线做法。
---
### 思路
线段树分治。
考虑到每条道路都有一个**寿命**，即从某时刻到某时刻里存在，我们具备了线段树分治的一个先决条件。**特别的，如果最后都没有死，我们最后杀掉它。**
我们维护一个**时光序列**，即某时刻中有的道路，那么对每条道路，我们**在时光序列的某段中同时插入**，最后对时光序列每个询问点进行查询即可，使用并查集复杂度是 $O(nm\alpha(n))$ 的。
~~这不就暴力吗。~~
考虑到时光序列可以形如一颗 Leafy Tree（把实际信息存在叶子节点的树）的，我们用线段树维护它，插入边时就是在线段树上区间插入，查询时 dfs 一遍线段树即可。
什么，你问我 dfs 时怎么统计贡献？
使用带撤销并查集即可。
什么，你不会带撤销并查集？
其实就是不用路径压缩而用其它优化（如按秩合并）的并查集，开栈记录下 `merge` 过程，撤销操作就取栈顶回退即可。
复杂度 $O(n+m\log m\log n)$。
---
### Code
带撤销并查集使用按秩合并没有精神，以下代码利用 Treap 的思想，封装了一个 `Heap_DSU`。
```cpp
#include <algorithm>
#include <map>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}
template<typename T,typename Rand>
class Heap_DSU
{
private:
std::vector<T>Fath,Prior,Hty;
T root(T p){return(p==Fath[p])?p:root(Fath[p]);}
public:
voi build(T n,Rand rng=Rand())
{
Fath.resize(n),Prior.resize(n),Hty.clear();
for(T i=0;i<n;i++)Fath[i]=i,Prior[i]=rng();
}
bol connected(uint u,uint v){return root(u)==root(v);}
bol merge(T u,T v)
{
if((u=root(u))==(v=root(v)))return Hty.push_back(u),false;
if(Prior[u]<Prior[v])std::swap(u,v);
return Fath[u]=v,Hty.push_back(u),true;
}
bol revoke()
{
if(Hty.empty())return false;
T p=Hty.back();Hty.pop_back();
if(Fath[p]==p)return false;
return Fath[p]=p,true;
}
};
typedef std::pair<uint,uint>Pair;
struct Seg
{
std::vector<Pair>Way;uint len;Seg*L,*R;
voi build(uint n){if((len=n)>1)L=new Seg,R=new Seg,L->build(len>>1),R->build(len-(len>>1));}
voi insert(uint l,uint r,Pair p)
{
if(!l&&r==len){Way.push_back(p);return;}
if(l<(len>>1))
if(r<=(len>>1))L->insert(l,r,p);
else L->insert(l,len>>1,p),R->insert(0,r-(len>>1),p);
else R->insert(l-(len>>1),r-(len>>1),p);
}
};
ullt Ra=1;const ullt Rb=10007,Rc=114513;struct rng{uint operator()(){return Ra=Ra*Rb+Rc;}};
Heap_DSU<uint,rng>U;
chr C[10];Pair P[114514];uint Op[114514];
bol Ans[114514];uint t=0;
uint hash(uint a,bol b){return a<<1|b;}
std::map<Pair,uint>M;Seg S;
voi dfs(Seg*S,uint cnt)
{
uint k=0;for(auto w:S->Way)U.merge(w.first,w.second),k++;
if(S->len==1)
{
if(!Op[cnt])Ans[t++]=U.connected(P[cnt].first,P[cnt].second);
}
else dfs(S->L,cnt),dfs(S->R,cnt+S->L->len);
while(k--)U.revoke();
}
int main()
{
uint n,m=0,r,c;scanf("%u%u",&n),U.build(n<<1);
while(scanf("%s",C)==1&&*C!='E')
{
Op[m]=*C=='A'?0:(*C=='O'?1:2);
scanf("%u%u",&r,&c),P[m].first=hash(c-1,r-1);
scanf("%u%u",&r,&c),P[m].second=hash(c-1,r-1);
if(P[m].first>P[m].second)std::swap(P[m].first,P[m].second);
m++;
}
S.build(m);
for(uint i=0;i<m;i++)if(Op[i]==1)M[P[i]]=i;else if(Op[i]==2)S.insert(M[P[i]],i,P[i]),M.erase(P[i]);
for(auto w:M)S.insert(w.second,m,w.first);
dfs(&S,0);
for(uint i=0;i<t;i++)puts(Ans[i]?"Y":"N");
return 0;
}
```
---
### 一些经验 / 非经验
可以离线（经验）：
* [SP9576](https://www.luogu.com.cn/problem/SP9576)
* [SP9577](https://www.luogu.com.cn/problem/SP9577)
* [loj121](https://loj.ac/p/121)
* [P2147](https://www.luogu.com.cn/problem/P2147)
* [P3767](https://www.luogu.com.cn/problem/P3767)
强制在线（非经验）：
* [loj122](https://loj.ac/p/122)
* [P5247](https://www.luogu.com.cn/problem/P5247)