https://www.lydsy.com/JudgeOnline/problem.php?id=2049
线段树真神奇
题意：给出一波操作，拆边加边以及询问两点是否联通。
听说常规方法是在线LCT，留坑。
如果说这个删边的操作是删除上一条边，那这自然是可撤销并查集的模板题，直接在线维护就可以了。
但是问题在于删除边的顺序是不可能固定的，要知道并查集是不可以随意撤销的。
万万没想到还有更加高妙的手法。
首先可以证明一条边的存在一定是一段或者多段连续的区间。
建立一条时间节点长度的线段树，结点维护一个边集合，每个位置表示的是当前这个时间下存在了哪几条边。
将上述的边区间全部加入，和常规的线段树不一样，这个不需要lazy标记也不需要Pushdown到下属区间，为了节省时间和空间，对于1 - N区间的边来说，我们仅仅把1号结点加上这条边。
然后用dfs的方法，进入结点时加上这些边，离开的时候删除这些边，在线段树的叶子节点上，并查集维护的就是当前时间的状态，离线的query直接询问即可。
时间复杂度，加边的整个过程mlogm,询问的过程节点数mlogm * 并查集find操作logm = mlog2 m
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
int read(){int x = ,f = ;char c = getchar();while (c<'' || c>''){if (c == '-') f = -;c = getchar();}
while (c >= ''&&c <= ''){x = x * + c - '';c = getchar();}return x*f;}
const double eps = 1e-;
const int maxn = 1e5 + ;
const int maxm = 2e6 + ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
int N,M,K;
struct Query{
int t,u,v;
Query(){}
Query(int t,int u,int v):t(t),u(u),v(v){}
}q[maxm];
struct Line{
int op,u,v;
Line(){}
Line(int op,int u,int v):op(op),u(u),v(v){}
}line[maxm];
map<PII,int>Q;
int Stack[maxm],top;
int size[maxn],fa[maxn];
void init(){
for(int i = ; i <= N ; i ++){
fa[i] = -; size[i] = ;
}
top = ;
}
//segment_tree
struct Tree{
int l,r;
int head;
}tree[maxm << ];
struct Edge{
PII data;
int next;
}edge[maxm << ];
int tot,cnt,cnt2;
void add(int u,PII v){
edge[tot].next = tree[u].head;
edge[tot].data = v;
tree[u].head = tot++;
}
void Build(int t,int l,int r){
tree[t].l = l; tree[t].r = r;
tree[t].head = -;
if(l == r) return;
int m = (l + r) >> ;
Build(t << ,l,m); Build(t << | ,m + ,r);
}
void update(int t,int l,int r,PII v){
if(l <= tree[t].l && tree[t].r <= r){
add(t,v);
return;
}
int m = (tree[t].l + tree[t].r) >> ;
if(r <= m) update(t << ,l,r,v);
else if(l > m) update(t << | ,l,r,v);
else{
update(t << ,l,m,v);
update(t << | ,m + ,r,v);
}
}
int find(int x){
while(fa[x] != -) x = fa[x];
return x;
}
void Union(int x,int y){
x = find(x); y = find(y);
if(x == y) return;
if(size[x] > size[y]) swap(x,y);
Stack[top++] = x;
fa[x] = y;
size[y] += size[x] + ;
}
void rewind(int t){
while(top > t){
int x = Stack[--top];
size[fa[x]] -= size[x] + ;
fa[x] = -;
}
}
void dfs(int t){
int now = top;
for(int i = tree[t].head; ~i; i = edge[i].next){
PII v = edge[i].data;
Union(v.fi,v.se);
}
if(tree[t].l == tree[t].r){
while(tot <= cnt2 && q[tot].t == tree[t].l){
if(find(q[tot].u) == find(q[tot].v)){
puts("Yes");
}else{
puts("No");
}
tot++;
}
rewind(now);
return;
}
dfs(t << ); dfs(t << | );
rewind(now);
}
int main(){
Sca2(N,M); init();
cnt = ,cnt2 = ;
for(int i = ; i <= M ; i ++){
char op[]; int u,v;
scanf("%s%d%d",op,&u,&v);
if(u > v) swap(u,v);
if(op[] == 'Q') q[++cnt2] = Query(cnt,u,v);
else if(op[] == 'C') line[++cnt] = Line(,u,v);
else line[++cnt] = Line(,u,v);
}
tot = ; Build(,,cnt);
for(int i = ; i <= cnt; i ++){
int &x = Q[mp(line[i].u,line[i].v)];
if(line[i].op == ) x = i;
else{
update(,x,i - ,mp(line[i].u,line[i].v));
x = ;
}
}
for(map<PII,int>::iterator it = Q.begin(); it != Q.end(); it++){
pair<PII,int> u = *it;
if(u.se) update(,u.se,cnt,u.fi);
}
tot = ;
dfs();
return ;
}