Reincarnation

正因为梦易碎，才格外美好。

线段树分治

发表于 更新于 分类于 ，
本文字数： 17k 阅读时长 ≈ 15 分钟

“恋如雨止，而大雨停滞之时，即吾殒命之日。”

大概是一个很 的东西。

做法

有 个操作作用在 的时间内的某个区间 上，最后求的是每一个时间的状态。

这是线段树分治求解的问题。显然对于每一个时间都重新求解肯定挂飞，所有操作 都有 。而线段树分治可以做到 ， 是题目操作复杂度和维护复杂度。

我们记录一棵时间戳线段树，其子结点维护的是某一个时刻的信息，其余结点维护某一段时间的信息。

一个很显然的例子：

一张有 个点和 条边的图，每一条边只会在时间 内出现。

那么我们遍历线段树，当当前区间 已经在某一条边的出现时间里了，我们就将其加入到图中，然后继续向下递归，然后当我们从其子区间出来的时候，再将这条边删去。

当然，删边操作说的轻松，做起来确实比较困难。所以要求线段树分治一般与可持久化数据结构或者可撤销数据结构一起使用。

例题

二分图

前置知识：可撤销并查集。

不想简化题意了。

大概就是一个线段树分治的板子，然后考虑如何能够快速地判定二分图，有一个大概的结论，可以用并查集 判断。

并查集扩展域是可以解决这个问题的（还有一个办法是挂边权），每次连边都连成 ，然后当 连通时，该图不是二分图，结论显然。

然后这道题就可做了，因为有回溯弹栈操作，所以考虑可撤销并查集。

每次查询一个区间并将其所有操作实现，判断连通。向下传递判定即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
// Problem: P5787 二分图 /【模板】线段树分治
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5787
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
	read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(char c)
{
	putchar(c);
}
template<>
inline void write(char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
	write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
	x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
	x=x<y?x:y;
}
const int MAXN=5e5+10,MAXM=1e6+10;
int N,M,K;
#define ls (p<<1)
#define rs (p<<1|1)
struct ST
{
	int l,r;
	std::vector<int>val;
}Tr[MAXN<<2];
struct Edges
{
	int fr,to;
}Ed[MAXM];
bool ans[MAXN];
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void modifyX(int p,int l,int r,int v)
{
	if(l>r) return ;
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val.push_back(v),void();
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyX(ls,l,r,v);
	if(mid<r) modifyX(rs,l,r,v);
}
struct Dsu
{
	int Rt[MAXN],Siz[MAXN],Stk[MAXN],Top;
	inline void init(int n){ for(int i=1;i<=n;++i) Rt[i]=i,Siz[i]=1; }
	inline int getRt(int x)
	{
		while(x!=Rt[x]) x=Rt[x];
		return x;
	}
	inline void merge(int u,int v)
	{
		// std:: cout << "merge: " << u << " " << v << std:: endl;
		int p=getRt(u),q=getRt(v);
		if(p==q) return ;
		if(Siz[p]<Siz[q]) std::swap(p,q);
		Siz[p]+=Siz[q],Rt[q]=p;
		Stk[++Top]=q;
	}
	inline void back()
	{
		int q=Stk[Top--];
		Siz[Rt[q]]-=Siz[q],Rt[q]=q;
	}
	inline void back(int x)
	{
		while(Top>x) back();
	}
	inline bool connect(int u,int v){ return (getRt(u)==getRt(v)); }
}Dsu;
void Divide_Conquer(int p,bool ok)
{
	int Tim=Dsu.Top;
	if(ok) for(int v:Tr[p].val)
	{
		Dsu.merge(Ed[v].fr,Ed[v].to+N);
		Dsu.merge(Ed[v].fr+N,Ed[v].to);
		if(Dsu.connect(Ed[v].fr,Ed[v].fr+N)||Dsu.connect(Ed[v].to,Ed[v].to+N))
		{
			ok=0;
			break;
		}
		// printf("%d:%d %d %d %d %d\n",p,Dsu.getRt(Ed[v].fr),Dsu.getRt(Ed[v].to),Tr[p].l,Tr[p].r,ok);
	}
	if(Tr[p].l==Tr[p].r) return ans[Tr[p].l]=ok,void();
	Divide_Conquer(ls,ok),Divide_Conquer(rs,ok);
	Dsu.back(Tim);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,M,K);
	Dsu.init(N+N+1);
	build(1,1,K);
	for(int i=1,u,v,l,r;i<=M;++i)
	{
		read(u,v,l,r);Ed[i]=(Edges){u,v};
		modifyX(1,l+1,r,i);
	}
	Divide_Conquer(1,1);
	for(int i=1;i<=K;++i) puts(ans[i]?"Yes":"No");
	return 0;
}
/*

*/

类双倍经验

https://codeforces.com/contest/813/problem/F

这个东西与板子题的不同在于，并没有把每一条边的出现时间给你给出来，而且每一条边都有可能会出现很多次，然后我们就可以记录一个 std::map 表示每一条边上一次出现的时间戳，而且为了方便线段树的传递，我们可以再来一个 std::map 来表示边 离散化之后的编号，然后记录一个 bool Cnt[] 来决定这条边是出现在 还是反集，然后就是板子了。

打了半个小时，还不是很熟练啊。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// ----- Eternally question-----
// Problem: CF813F Bipartite Checking
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF813F
// Memory Limit: 250 MB
// Time Limit: 6000 ms
// Written by: Eternity
// Time: 2022-11-03 20:05:01
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
const int MAXN=2e5+10;
int N,Q,Idx;
struct Edges
{
	int fr,to;
	bool operator<(Edges x){ return fr==x.fr?to<x.to:fr<x.fr; }
}Ed[MAXN],Edge[MAXN];
std::map<int,int>Mp[MAXN],Id[MAXN];
bool Cut[MAXN],ans[MAXN];
std::vector<int>val[MAXN<<2];
#define ls (p<<1)
#define rs (p<<1|1)
void modifyCover(int p,int l,int r,int ql,int qr,int v)
{
	if(ql<=l&&r<=qr) return val[p].push_back(v),void();
	int mid=(l+r)>>1;
	if(ql<=mid) modifyCover(ls,l,mid,ql,qr,v);
	if(mid<qr) modifyCover(rs,mid+1,r,ql,qr,v);
}
struct Dsu
{
	int Rt[MAXN],Siz[MAXN],Stk[MAXN],Top;
	inline void init(int n){ for(int i=1;i<=n;++i) Rt[i]=i,Siz[i]=1; }
	inline int getRt(int x)
	{
		while(x!=Rt[x]) x=Rt[x];
		return x;
	}
	inline void merge(int u,int v)
	{
		int p=getRt(u),q=getRt(v);
		if(p==q) return ;
		if(Siz[p]<Siz[q]) std::swap(p,q);
		Siz[p]+=Siz[q],Rt[q]=p;
		Stk[++Top]=q;
	}
	inline void back()
	{
		int q=Stk[Top--];
		Siz[Rt[q]]-=Siz[q],Rt[q]=q;
	}
	inline void back(int x){ while(Top>x) back(); }
	inline bool connect(int u,int v){ return (getRt(u)==getRt(v)); }
}Dsu;
void Divide_Conquer(int p,int l,int r,bool ok)
{
	// printf("search:%d %d %d %d\n",p,l,r,ok);
	int Tim=Dsu.Top;
	if(ok) for(int x:val[p])
	{
		auto e=Edge[x];
		// printf("merge:%d %d\n",e.fr,e.to);
		Dsu.merge(e.fr,e.to+N),Dsu.merge(e.to,e.fr+N);
		if(Dsu.connect(e.fr,e.fr+N)||Dsu.connect(e.to,e.to+N))
		{
			ok=0;
			break;
		}
	}
	int mid=(l+r)>>1;
	if(l==r) return ans[l]=ok,void();
	Divide_Conquer(ls,l,mid,ok),Divide_Conquer(rs,mid+1,r,ok);
	Dsu.back(Tim);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q);
	Dsu.init(N+N+1);
	for(int i=1;i<=Q;++i)
	{
		read(Ed[i].fr,Ed[i].to);
		if(!Id[Ed[i].fr][Ed[i].to])
		{
			Edge[++Idx]=(Edges){Ed[i].fr,Ed[i].to};
			Id[Ed[i].fr][Ed[i].to]=Idx;
		}
	}
	for(int i=1;i<=Q;++i)
	{
		auto e=Ed[i];
		int id=Id[e.fr][e.to];
		if(Cut[id])
		{
			modifyCover(1,1,Q,Mp[e.fr][e.to],i-1,id);
			// write(Mp[e.fr][e.to],' ',i,'\n');
		}
		else Mp[e.fr][e.to]=i;
		Cut[id]^=1;
	}
	for(int i=1;i<=Idx;++i)
		if(Cut[Id[Edge[i].fr][Edge[i].to]])
		{
			modifyCover(1,1,Q,Mp[Edge[i].fr][Edge[i].to],Q,i);
			// write(Mp[Edge[i].fr][Edge[i].to],' ',Q,'\n');
		}
	Divide_Conquer(1,1,Q,1);
	for(int i=1;i<=Q;++i) puts(ans[i]?"YES":"NO");
	return 0;
}
/*

*/

Pastoral Oddities

神仙题， 当例题讲。

对于一个边集中每个点的度数为奇数的充要条件是——这个图只存在大小为偶数的连通块。

然后要求最小化边集中的最大边权，可以想到有最小生成树，所以可以贪心选取，使用 来解决，当然，每一次询问都给出 显然不可做，只能借鉴思想。

  • 把边按权值排序，用并查集时刻维护一下奇连通块的数目就行了。

但这是离线做法。然后考虑动态加边，这样的话，可以考虑每一条边最后被淘汰的时间戳，那么一条边 其影响答案的区间如果为 ，有点像是线段树分治的样子，就往那边想。

然后乱搞。我不会了

最后时间复杂度 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// ----- Eternally question-----
// Problem: CF603E Pastoral Oddities
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF603E
// Memory Limit: 250 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2022-11-03 17:29:30
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=3e5+10,MAXM=3e5+10;
int N,M,Pos,ans[MAXN],Odd;
struct Edges
{
	int fr,to,val,id;
	bool operator<(const Edges &x){ return val<x.val; }
}Ed[MAXM];
struct Node
{
	int fr,to,delta;
}Stk[MAXM];
int Rt[MAXN],Siz[MAXN],Top;
int getRt(int x){ return Rt[x]==x?x:getRt(Rt[x]); }
std::vector<Edges>Vec[MAXM<<2];
#define ls (p<<1)
#define rs (p<<1|1)
void modifyCover(int p,int l,int r,int ql,int qr,Edges v)
{
	if(ql>qr) return ;
	if(ql<=l&&r<=qr) return Vec[p].push_back(v),void();
	int mid=(l+r)>>1;
	if(ql<=mid) modifyCover(ls,l,mid,ql,qr,v);
	if(mid<qr) modifyCover(rs,mid+1,r,ql,qr,v);
}
inline void merge(int u,int v)
{
	int p=getRt(u),q=getRt(v);
	if(p!=q)
	{
		if(Siz[p]<Siz[q]) p^=q^=p^=q;
		Stk[++Top]=(Node){p,q,0};
		if((Siz[p]%2==1)&&(Siz[q]%2==1)) Odd-=2,Stk[Top].delta+=2;
		Siz[p]+=Siz[q],Rt[q]=p;
	}
}
void Divide_Conquer(int p,int l,int r)
{
	int Tim=Top;
	for(auto i:Vec[p]) merge(i.fr,i.to);
	int mid=(l+r)>>1;
	if(l==r)
	{
		while(true)
		{
			if(!Odd||Pos>=M) break;
			if(Ed[Pos+1].id<=l)
			{
				merge(Ed[Pos+1].fr,Ed[Pos+1].to);
				modifyCover(1,1,M,Ed[Pos+1].id,l-1,Ed[Pos+1]);
			}
			++Pos;
		}
		if(!Odd) ans[l]=Ed[Pos].val;
		else ans[l]=-1;
	}
	else Divide_Conquer(rs,mid+1,r),Divide_Conquer(ls,l,mid);
	while(Top^Tim)
	{
		int fr=Stk[Top].fr,to=Stk[Top].to,delta=Stk[Top].delta;
		Siz[fr]-=Siz[to],Rt[to]=to,Odd+=delta,--Top;
	}
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,M);Odd=N;
	for(int i=1;i<=N;++i) Rt[i]=i,Siz[i]=1;
	for(int i=1;i<=M;++i) read(Ed[i].fr,Ed[i].to,Ed[i].val),Ed[i].id=i;
	std::sort(Ed+1,Ed+M+1),Divide_Conquer(1,1,M);
	for(int i=1;i<=M;++i) write(ans[i],'\n');
	return 0;
}
/*

*/

动态图连通性

题目简介

题目名称：动态图连通性「离线可过」
题目来源：

评测链接 ：https://loj.ac/p/121
评测链接 ：https://www.luogu.com.cn/problem/P4246

形式化题意：有一张有 个结点的图，现在有 次操作形如：

  1. 加入一条边 ；
  2. 删除一条边 ；
  3. 查询 是否连通。

数据范围：

因为是图，所以用 暴力维护会爆炸，但是仅仅维护连通性，所以可以考虑使用并查集，又因为有删除操作，所以考虑使用可撤销并查集，把每一条边用哈希存储，直到其被删除则在该区间添加该边，然后照常跑线段树分治即可。

时间复杂度 ，好像是有一支 的做法，但是那个好像是在线的，不管。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// ----- Eternally question-----
// Problem: #121. 「离线可过」动态图连通性
// Contest: LibreOJ
// URL: https://loj.ac/p/121
// Memory Limit: 512 MB
// Time Limit: 800 ms
// Written by: Eternity
// Time: 2023-06-30 20:49:02
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
struct Dsu
{
	int Rt[MAXN],Siz[MAXN],Stk[MAXN],Top;
	inline void init(int n){ for(int i=1;i<=n;++i) Rt[i]=i,Siz[i]=1; }
	inline int getRt(int x)
	{
		while(x!=Rt[x]) x=Rt[x];
		return x;
	}
	inline void merge(int u,int v)
	{
		int p=getRt(u),q=getRt(v);
		if(p==q) return ;
		if(Siz[p]<Siz[q]) std::swap(p,q);
		Siz[p]+=Siz[q],Rt[q]=p;
		Stk[++Top]=q;
	}
	inline void back()
	{
		int q=Stk[Top--];
		Siz[Rt[q]]-=Siz[q],Rt[q]=q;
	}
	inline void back(int x){ while(Top>x) back(); }
	inline bool connect(int x,int y){ return (getRt(x)==getRt(y)); }
}Dsu;
using Pir=std::pair<int,int>;
int N,Q,query[MAXN];
char opt[10];
struct Edges
{ int fr,to; }Ed[MAXN];
bool ans[MAXN];
std::map<Pir,int>Hash;
#define ls (p<<1)
#define rs (p<<1|1)
#define Mkr(x,y) std::make_pair(x,y)
struct Segment
{
	int l,r;
	std::vector<int>val;
}Tr[MAXN<<2];
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void InsertX(int p,int l,int r,int v)
{
	if(l>r) return ;
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val.emplace_back(v),void();
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) InsertX(ls,l,r,v);
	if(mid<r) InsertX(rs,l,r,v);
}
void DAC(int p)
{
	int Tim=Dsu.Top;
	for(int v:Tr[p].val) if(query[v]) Dsu.merge(Ed[v].fr,Ed[v].to);
	for(int v:Tr[p].val) if(!query[v]) ans[v]=Dsu.connect(Ed[v].fr,Ed[v].to);
	if(Tr[p].l==Tr[p].r) return ;
	DAC(ls),DAC(rs);
	Dsu.back(Tim);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	Dsu.init(N);
	build(1,1,Q);
	for(int i=1,opt,u,v;i<=Q;++i)
	{
		read(opt,u,v);
		if(u>v) std::swap(u,v);
		Ed[i]=(Edges){u,v};
		if(opt==0) Hash[Mkr(u,v)]=i;
		if(opt==1)
		{
			InsertX(1,Hash[Mkr(u,v)],i-1,i);
			Hash.erase(Hash.find(Mkr(u,v)));
		}
		if(opt==2) InsertX(1,i,i,i),query[i]=0;
		else query[i]=1;
	}
	for(auto x:Hash) InsertX(1,x.second,Q,x.second);
	DAC(1);
	for(int i=1;i<=Q;++i) if(!query[i]) puts(ans[i]?"Y":"N");
	return 0;
}
/*

*/
相关文章