自动搬运

查看原文

来自洛谷，原作者为

	ArrTue ac

搬运于2025-08-24 22:12:41，当前版本为作者最后更新于2021-11-22 15:32:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

前置知识：

Link-Cut Tree。

题意简述：

• 有 $n$ 个未知数 $a_{1\dots n}$，每个数在 $[0,2^k)$ 范围内，$q$ 次操作，分为三种：

  1. 给出一条信息：$a_{l\dots r}$ 异或和为 $val$。
  2. 撤回第 $cnt$ 次操作 1。
  3. 询问有多少种 $a$ 序列满足当前未被撤回的操作 1。

• $n\le2\times10^5$，$q\le10^6$，$k\le30$。

分析：

记 $s_i$ 为 $a_{1\dots i}$ 的异或和，则操作 1 的信息即为 $s_{l-1}\operatorname{xor}s_r=val$。这意味着确定了 $s_{l-1}$ 和 $s_r$ 的其中一个，另一个就会被确定。将操作 1 抽象为在 $s_{l-1}$ 与 $s_r$ 之间连一条权值为 $val$ 的边，则对于一个连通块，当其中一个 $s$ 确定后，其他也均可确定。

从左到右依次考虑 $a_i$ 的可能取值。考虑 $s_i$ 的值，如果 $s_{0\dots i-1}$ 中至少有一个与 $s_i$ 在同一个连通块内，那么 $s_i$ 就会被确定，$a_i$ 能且仅能取 $s_i\operatorname{xor}s_{i-1}$。否则由于 $s_i$ 能取任意值，$a_i$ 也能取任意值，有 $2^k$ 种方案。

故对于一个连通块，只有其中标号最小的有可能取最任意值（若标号最小的是 $s_0$，则只有一种取值，即 $0$；否则标号最小的有 $2^k$ 种方案），其他数都可以由这个标号最小的确定。故方案数是 $2^{k(m-1)}$，$m$ 代表连通块数量。

特殊地，当两条操作 1 矛盾时，没有情况满足条件，应输出 $0$。

这样问题就转化成：加边，删边，询问连通块数以及边权是否矛盾。

先不考虑边权，只考虑连通块数量。此时操作 1 不会产生矛盾。

如果保证图是森林，则显然可以使用 LCT 维护。考虑怎么把一般的连通图转化为树的情况。

注意到如果要删除的边在某一个环上，则该边的两个端点在删除前后均连通，即删除该边对连通性无影响，不如提前删掉该边。即每次加入一条边，对于形成的环，我们直接删掉该环中最早将被删的边。这样，每次加边都不会形成环，转化成了之前的情况。

现在考虑边权。新边的两个端点之间无边时，两点之间无限制关系，不会产生矛盾；有边时，若两点之间边权异或和不同于新边的边权，则产生矛盾，且矛盾会一直持续到该新边被删除或环上最早将被删的边被删除。

复杂度均摊 $\mathcal O(q\log n)$。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
#pragma GCC diagnostic ignored "-Wparentheses"
using namespace std;
typedef long long ll;
inline ll read() {
	ll res=0; bool k=1; char ch;
	while(!isdigit(ch=getchar())) k=ch^45;
	do res=res*10+(ch&15); while(isdigit(ch=getchar()));
	return k? res: -res;
}
inline void swap_(int &x, int &y) {int t_=x; x=y, y=t_;}
inline void to_max(int &x, int y) {if(x<y) x=y;}
inline int min_(int x, int y) {return x<y? x: y;}
const int mN=2e5+9, mQ=1e6+9, mS=mN+mQ, modn=998244353;
int n, q, k, cnt, ans, p[mN];   //p 为 2^ki 的预处理
int opt[mQ], cut[mQ], tim[mS], a[mQ][2];
//操作类型、删掉的边标号、边被删的时间、边的两端点

namespace LCT {
	#define lc tr[p].son[0]
	#define rc tr[p].son[1]
	#define f tr[p].fa
	struct Node {
		int fa, son[2], mn; //mn 为最早被删边的标号
		ll val, sum;    //边权，边权和
		bool rev;
	} tr[mS];
	inline bool which(int p) {return tr[f].son[1]==p;}
	inline bool is_rt(int p) {return !f || tr[f].son[0]^p && tr[f].son[1]^p;}
	inline void push_up(int p) {
		tr[p].mn=tr[tr[p].son[tim[tr[rc].mn]<tim[tr[lc].mn]]].mn;
		if(tim[p]<tim[tr[p].mn]) tr[p].mn=p;
		tr[p].sum=tr[p].val^tr[lc].sum^tr[rc].sum;
	}
	inline void push_down(int p) {
		if(!tr[p].rev) return;
		swap_(tr[lc].son[0], tr[lc].son[1]), tr[lc].rev^=1;
		swap_(tr[rc].son[0], tr[rc].son[1]), tr[rc].rev^=1;
		tr[p].rev=0;
	}
	inline void rotate(int p) {
		int x=f, fx=tr[x].fa;
		bool wp=which(p), wx=which(x), isrtx=is_rt(x);
		if(tr[p].son[wp^1]) tr[tr[p].son[wp^1]].fa=x;
		tr[x].son[wp]=tr[p].son[wp^1];
		tr[x].fa=p, tr[p].son[wp^1]=x, f=fx;
		if(!isrtx) tr[fx].son[wx]=p;
		push_up(x), push_up(p);
	}
	int sta[mS], top;
	void splay(int p) {
		for(int x=sta[top=1]=p; !is_rt(x); ) sta[++top]=x=tr[x].fa;
		while(top) push_down(sta[top--]);
		for(; !is_rt(p); rotate(p)) if(!is_rt(f)) rotate(which(f)^which(p)? p: f);
	}
	inline void access(int p) {for(int x=0; p; x=p, p=f) splay(p), rc=x, push_up(p);}
	inline void make_rt(int p) {access(p), splay(p), swap_(lc, rc), tr[p].rev^=1;}
	inline int find_rt(int p) {
		for(access(p), splay(p); lc; ) push_down(p=lc);
		return splay(p), p;
	}
	#undef lc
	#undef rc
	#undef f
}
using namespace LCT;
inline void e_cut(int p) {
	make_rt(p);
	access(a[p-n-1][0]), splay(p), tr[a[p-n-1][0]].fa=0, tr[p].son[1]=0;
	access(a[p-n-1][1]), splay(p), tr[a[p-n-1][1]].fa=0;
}

int main() {
	n=read(), q=read(), k=read();
	p[0]=1, p[1]=(1ll<<k)%modn;
	rep(i, 2, ans=n+1) p[i]=(ll) p[i-1]*p[1]%modn;
	rep(i, 0, n+q+1) tim[i]=q+1, tr[i].mn=i;    //初始化
	rep(i, 1, q) {
		if((opt[i]=read())==0) ++cnt, a[cnt][0]=read(), a[cnt][1]=read()+1, tr[n+1+cnt].sum=tr[n+1+cnt].val=read();
        //因为不想让 a[i][0]=0，故两者均 +1：l-1 -> l； r -> r+1
		else if(opt[i]==1) tim[cut[i]=n+1+read()]=i;
	}
	cnt=0;
	int mx=0;
	rep(i, 1, q) if(opt[i]==0) {
		++cnt;
		int u=a[cnt][0], v=a[cnt][1], t=tim[n+1+cnt];
        make_rt(u);
        int rt_v=find_rt(v);
		if(rt_v^u) {    //u,v 不在同一连通块中
			--ans;
			swap_(tr[rt_v].son[0], tr[rt_v].son[1]), tr[rt_v].rev^=1;   //相当于 make_rt(v)
			tr[rt_v].fa=tr[u].fa=n+1+cnt;   //相当于 link(u, n+1+cnt), link(v, n+1+cnt)
		} else {
			int id=tr[u].mn;
			if(tr[u].sum^tr[n+1+cnt].val) to_max(mx, min_(tim[id], t));
            //如果不相同，则到 min(tim[id], t) 之前均会矛盾
			if(tim[id]<t) { //最先被删除的边是 id
				e_cut(id), cut[tim[id]]=0;  //标记被删过
				make_rt(cnt+n+1);  
				make_rt(u), splay(u), tr[u].fa=cnt+n+1; //link(u, cnt+n+1)
				make_rt(v), splay(v), tr[v].fa=cnt+n+1; //link(v, cnt+n+1
			} else cut[t]=0;    //最先被删的边是 t，直接不加了
		}
	} else if(opt[i]==1) {
		if(cut[i]) ++ans, e_cut(cut[i]);
	} else printf("%d\n", i<=mx? 0: p[ans-1]);
	return 0;
}