前言

后续把这个比赛的其他题目一起补上来吧。

G

题目

这道题目思路还是很简单的。

首先考虑图权值最优下限，肯定就是度数是奇数的点数个数，但是是不是一定能到达这个下限呢？基本上只要能想懂这个的证明就知道该怎么做了。

先提供暴力思路：

一个十分明显的思路是，把一个奇数点找到一个与与他相联通的奇数点，然后合成成一条路径，在原图中去掉这条路径，这条路径作为一个子图，其上面的点除了端点外的其余点的度数都是偶数，所以只要我们边红蓝相邻染色就可以完成端点颜色特异，其余点相连的红色边和蓝色边数量相同。

而去掉若干条路径的原图度数都是偶数，则直接欧拉回路，也是红蓝染色，这样构造，就可以达到下限。

思考怎么维护？

一个非常粗暴的方法就是直接维护一个平衡树，其中每个点的附加权值是边的编号，而这个平衡树的中序遍历可以还原这个路径从一个端点走到另一个端点所走过的编号。

这样，考虑连上的边，要么出现一条新的路径，长度为 $1$ ，要么延长原有路径，要么合并原有路径，要么把路径变为回路，变为回路直接暴力把回路遍历就行了，因为一条边最多变为一次路径，再变为回路也只会被遍历一遍，此后就都在回路中存在了，所以这个操作整体是 $O(m+q)$ 的。

当然，因为中间涉及到了平衡树，所以$O((m+q)\log{(m+q)})$。

当然，输出的时间复杂度暴力遍历就行啦。

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define  N  410000
using  namespace  std;
typedef  long  long  LL;
const  LL  mod=998244353;
template<class  T>
inline  void  zwap(T  &x,T  &y){x^=y^=x^=y;}
int  e[N];int  ecnt;
LL  v2[N];//2^i
LL  has=0;
 
struct  node
{
	int  y,next;
	bool  bk;
}a[N];int  len=1,last[N],du[N];
inline  void  ins(int  x,int  y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;du[y]++;}
int  root[N],rcnt,lian[N][2];
LL  rval[N][2];
int  be[N];
inline  void  xiao(int  x){(has-=rval[x][0]-mod)%=mod;}
inline  void  tian(int  x){(has+=rval[x][0])%=mod;}
 
int  siz[N],val[N],key[N],son[N][2],cnt;
bool  lazy[N];
inline  void  pushlazy(int  x)
{
	zwap(son[x][0],son[x][1]);
	lazy[x]^=1;
}
inline  void  plazy(int  id)
{
	zwap(lian[id][0],lian[id][1]);
	zwap(rval[id][0],rval[id][1]);
	pushlazy(root[id]);
}
inline  void  pushup(int  x){siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;}
inline  void  pushdown(int  x)
{
	if(lazy[x])lazy[x]=0,pushlazy(son[x][0]),pushlazy(son[x][1]);
}
inline  int  mer(int  A,int  B)
{
	if(!A   ||  !B)return  A+B;
	if(val[A]<=val[B])pushdown(A),son[A][1]=mer(son[A][1],B),pushup(A);
	else  pushdown(B),son[B][0]=mer(A,son[B][0]),pushup(B),zwap(A,B);
	return  A;
}
inline  void  add(int  k,int  to,int  type)
{
	if(type==1)
	{
		if(siz[root[to]]&1)(rval[to][1]+=v2[k])%=mod;
		else  (rval[to][0]+=v2[k])%=mod,(has+=v2[k])%=mod;
	}
	else
	{
		xiao(to);zwap(rval[to][0],rval[to][1]);
		(rval[to][0]+=v2[k])%=mod;tian(to);
	}
	cnt++;siz[cnt]=1;val[cnt]=rand();key[cnt]=k;
	if(!type)root[to]=mer(cnt,root[to]);
	else  root[to]=mer(root[to],cnt);
}
inline  void  he(int  x,int  y,int  t1,int  t2,int  k)
{
	if(t1==0)
	{
		if(!(siz[root[x]]&1))zwap(rval[x][0],rval[x][1]),(has+=rval[x][0]-rval[x][1]+mod)%=mod;
		zwap(lian[x][0],lian[x][1]);
		pushlazy(root[x]);
	}
	add(k,x,1);
	if(t2==1)
	{
		if(!(siz[root[y]]&1))zwap(rval[y][0],rval[y][1]),(has+=rval[y][0]-rval[y][1]+mod)%=mod;
		zwap(lian[y][0],lian[y][1]);
		pushlazy(root[y]);
	}
	xiao(x);xiao(y);
	be[lian[x][1]]=be[lian[y][0]]=0;be[lian[y][1]]=x;
	lian[x][1]=lian[y][1];
	if(siz[root[x]]&1)(rval[x][0]+=rval[y][1])%=mod,(rval[x][1]+=rval[y][0])%=mod;
	else  (rval[x][0]+=rval[y][0])%=mod,(rval[x][1]+=rval[y][1])%=mod;
	root[x]=mer(root[x],root[y]);
	tian(x);
}
 
inline  void  dfs1(int  x,int  id,int  co)
{
	if(du[x]&1)
	{
		lian[id][1]=x;du[x]--;
		be[x]=id;
		return  ;
	}
	for(int  &k=last[x];k;)
	{
		if(a[k].bk==0)
		{
			a[k].bk=1,a[k^1].bk=1;
			int  y=a[k].y;
			add(k/2,id,1);
			k=a[k].next;
			dfs1(y,id,co^1);
			return  ;
		}
		k=a[k].next;
	}
}
bool  shi[N];
inline  void  dfs2(int  x,int  co)
{
	shi[x]=1;
	for(int  &k=last[x];k;)
	{
		int  y=a[k].y;
		if(a[k].bk==0)
		{
			a[k].bk=a[k^1].bk=1;e[k/2]=co;
			if(co==0)(has+=v2[k/2])%=mod;
			k=a[k].next;
			dfs2(y,co^1);
		}
		else  k=a[k].next;
	}
}
int  sta[N],top;
inline  void  dfs3(int  x)
{
	if(!x)return  ;
	pushdown(x);
	dfs3(son[x][0]);
	sta[++top]=key[x];
	dfs3(son[x][1]);
}
inline  void  fu(int  x)
{
	top=0;dfs3(root[x]);
	for(int  i=1;i<=top;i++)e[sta[i]]=!(i&1);
}
inline  void  mie(int  x)
{
	fu(x);
	be[lian[x][0]]=be[lian[x][1]]=0;
}
int  n1,n2,m,n;
int  main()
{
	scanf("%d%d%d",&n1,&n2,&m);n=n1+n2;ecnt=m;
	v2[0]=1;for(int  i=1;i<=400000;i++)v2[i]=(v2[i-1]*2)%mod;
	for(int  i=1;i<=m;i++)
	{
		int  x,y;scanf("%d%d",&x,&y);y+=n1;
		ins(x,y);ins(y,x);
		
	}
	
	for(int  i=1;i<=n;i++)
	{
		if(du[i]&1)
		{
			du[i]--;be[i]=++rcnt;
			lian[rcnt][0]=i;
			dfs1(i,rcnt,0);
		}
	}
	for(int  i=1;i<=n;i++)
	{
		if(!shi[i])dfs2(i,0);
	}
	int  q;scanf("%d",&q);
	for(int  i=1;i<=q;i++)
	{
		int  type;scanf("%d",&type);
		if(type==1)
		{
			int  x,y;scanf("%d%d",&x,&y);y+=n1;
			++ecnt;
			
			if(be[x]  &&  be[y])
			{
				if(be[x]==be[y])
				{
					mie(be[x]),e[ecnt]=1;
				}
				else  he(be[x],be[y],lian[be[x]][1]==x,lian[be[y]][1]==y,ecnt);
			}
			else  if(be[x]+be[y]>0)
			{
				int  rt=be[x]+be[y],pi=be[x]?x:y;
				if(lian[rt][0]==pi)
				{
					add(ecnt,rt,0);
					be[lian[rt][0]]=0;be[lian[rt][0]=pi^x^y]=rt;
				}
				else
				{
					add(ecnt,rt,1);
					be[lian[rt][1]]=0;be[lian[rt][1]=pi^x^y]=rt;
				}
			}
			else
			{
				be[x]=be[y]=++rcnt;lian[rcnt][0]=x;lian[rcnt][1]=y;
				add(ecnt,rcnt,1);
			}
			printf("%lld\n",has);
			fflush(stdout);
		}
		else
		{
			int  rans=0;
			for(int  i=1;i<=n;i++)
			{
				if(be[i]  &&  lian[be[i]][0]==i)fu(be[i]);
			}
			for(int  i=1;i<=ecnt;i++)
			{
				if(e[i]==0)rans++;
			} 
			printf("%d ",rans);
			for(int  i=1;i<=ecnt;i++)
			{
				if(e[i]==0)printf("%d ",i);
			} 
			printf("\n");
			fflush(stdout);
		}
	}
	return  0;
}

当然，可不可以更快？

当然可以。

看以上过程，发现，我们平衡树可以维护整个路径，但是有必要吗？

没有必要，我们只要记录这条边在路径上的奇偶位置即可。

那么就用并查集维护，时间复杂度 ：$O(nα(n))$。（具体的可以看https://www.luogu.com.cn/blog/Troverld/solution-cf1499g）

下面仅仅口胡，感觉是正确的，欢迎 diss 。

但是如果你仔细的观察一下代码，你就会发现维护平衡树的部分和维护链信息的部分其实根本就不互相干扰，因此我们其实可以把平衡树部分拖到 $2$ 询问一次解决。

具体的，维护链信息的 $Hash$ 值的代码不变，但是，链的形态每变一次，就新建一个链并向原本的链连边，边信息就是改变的信息，同时合理安排左右儿子（左儿子的链在次链的左边，右儿子同理），然后在询问的时候从上到下模拟，同时带上翻转标记，这样处理就可以单次询问 $O(m)$ ，修改询问 $O(1)$ 了。（当然，路径变成回路还是要处理）

时间复杂度喜闻乐见的 $O(m+q)$ 。（但是因为这道题目我调试都已经调吐了，就不想再打这道题目了）

有趣的事情

我看错输出格式发了个帖子问人。。。

main函数中du[i]&1写成du[i]==1调了一个下午。。。

为了交代码把打代码时的所有中文注释全删了。（但是这么丑陋的代码估计加了注释也不会有人看吧）