题解

题目分析

这是一道基于位运算和图论的题目，需要使用位集优化大规模图的操作。

解题思路

1. 问题建模

• 构建有向图，节点数为 $n$，边数为 $m$
• 每条边有权重，使用位集 EJZ 存储
• 需要处理大规模图的位运算操作

2. 位集设计

• 使用 ull a[16] 存储 1024 位的位集
• 实现位运算操作：^（异或）、&（与）、|（或）
• 支持单点查询：get(EJZ &x, ll pos)

3. 图结构

• 定义边结构：Edge {u, v, tl, tr, w}
• 每条边有起点、终点、时间范围和权重
• 使用位集存储边的权重信息

4. 位运算优化

• 使用位运算加速集合操作
• 实现高效的位集合并和查询
• 支持大规模数据的快速处理

5. 关键技巧

• 使用 1ull << (pos % 64) 进行位操作
• 位集大小：$16 \times 64 = 1024$ 位
• 支持高效的集合运算

6. 算法实现

• 使用位集优化图遍历
• 实现高效的路径查找
• 支持动态更新图结构

时间复杂度

$O(n^2 / 64)$，通过位运算优化常数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const ll MAXN=1000,MAXQ=1000;
struct EJZ{
	ull a[16];
}ls,dwy;
struct Edge{
	ll u,v,tl,tr;
	EJZ w;
}e[MAXQ*2+5];
EJZ operator ^(const EJZ &x,const EJZ &y){
	for(int i=0;i<16;i++) ls.a[i]=(x.a[i]^y.a[i]);
	return ls;
}
EJZ operator &(const EJZ &x,const EJZ &y){
	for(int i=0;i<16;i++) ls.a[i]=(x.a[i]&y.a[i]);
	return ls;
}
EJZ operator |(const EJZ &x,const EJZ &y){
	for(int i=0;i<16;i++) ls.a[i]=(x.a[i]|y.a[i]);
	return ls;
}
bool get(EJZ &x,ll pos){
	return x.a[pos/64]&(1ull<<(pos%64));
}
bool Empty(EJZ &x){
	for(int i=0;i<16;i++) if(x.a[i]!=0) return false;
	return true;
}
EJZ Max(EJZ &x,EJZ &y){
	for(int i=15;i>=0;i--){
		if(x.a[i]<y.a[i]) return y;
		if(x.a[i]>y.a[i]) return x;
	}
	return x;
}
ll n,m,q,dep[505],fa[505],edcnt,FA[9][505],cnta,nn[MAXQ+5];
EJZ bz[9][505],a[MAXN+5],ans[MAXQ+5];
vector<pair<ll,EJZ> > E[505];
stack<ll> cz;
ll found(ll x){
	return x==fa[x]?x:(fa[x]=found(fa[x]));
}
void dfs(ll h,ll fat){
	FA[0][h]=fat;
	dep[h]=dep[fat]+1;
	for(int i=1;i<9;i++){
		FA[i][h]=FA[i-1][FA[i-1][h]];
		bz[i][h]=(bz[i-1][h]^bz[i-1][FA[i-1][h]]);
	}
	for(auto x:E[h]){
		if(x.first!=fat){
			bz[0][x.first]=x.second;
			dfs(x.first,h);
		}
	}
}
void Insert(EJZ x){
	for(int i=MAXN-1;i>=0;i--){
		if(get(x,i)){
			if(Empty(a[i])){
				cz.push(i);
				a[i]=x;
				return ;
			}
			x=(x^a[i]);
		}
	}
}
EJZ Query_max(){
	EJZ ans=dwy;
	for(ll i=MAXN-1;i>=0;i--){
		EJZ x=(ans^a[i]);
		ans=Max(ans,x);
	}
	return ans;
}
ll lca(ll x,ll y){
	if(dep[x]>dep[y]) swap(x,y);
	for(int i=8;i>=0;i--) if(dep[y]-(1<<i)>=dep[x]) y=FA[i][y];
	if(x==y) return x;
	for(int i=8;i>=0;i--) if(FA[i][x]!=FA[i][y]) x=FA[i][x],y=FA[i][y];
	return FA[0][x];
}
EJZ Pat(ll x,ll y){
	ll t=lca(x,y);
	EJZ ans=dwy;
	for(int i=8;i>=0;i--){
		if(dep[x]-(1<<i)>=dep[t]){
			ans=(ans^bz[i][x]);
			x=FA[i][x];
		}
	}
	for(int i=8;i>=0;i--){
		if(dep[y]-(1<<i)>=dep[t]){
			ans=(ans^bz[i][y]);
			y=FA[i][y];
		}
	}
	return ans;
}
void solve(ll l,ll r,vector<ll> edg){
	ll sjc=cz.size(),mid=(l+r)/2;
	vector<ll> nex;
	for(auto &x:edg){
		if(e[x].tl<=l&&e[x].tr>=r){
			EJZ ls=Pat(e[x].u,e[x].v);
			ls=(ls^e[x].w);
			Insert(ls);
			x=-x;
		}
	}
	if(l==r){
		ans[l]=Query_max();
	}
	else{
		for(auto x:edg){
			if(x>0&&e[x].tr>=l&&e[x].tl<=mid){
				nex.push_back(x);
			}
		}
		solve(l,mid,nex);
		nex.clear();
		for(auto x:edg){
			if(x>0&&e[x].tr>=mid+1&&e[x].tl<=r){
				nex.push_back(x);
			}
		}
		solve(mid+1,r,nex);
	}
	while(cz.size()>sjc){
		a[cz.top()]=dwy;
		cz.pop();
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		ll u,v;cin>>u>>v;
		string s;cin>>s;
		reverse(s.begin(),s.end());
		EJZ lls=dwy;
		for(int j=0;j<16;j++) for(int k=j*64,p=0;p<64;k++,p++) if(s.size()>k&&s[k]=='1') lls.a[j]|=(1ull<<p);
		ll U=found(u),V=found(v);
		if(U==V){
			++edcnt;
			e[edcnt].u=u;e[edcnt].v=v;e[edcnt].tl=0;e[edcnt].tr=q;e[edcnt].w=lls;
		}
		else{
			fa[U]=V;
			E[u].push_back(make_pair(v,lls));
			E[v].push_back(make_pair(u,lls));
		}
	}
	bz[0][1]=dwy;
	dfs(1,0);
	for(int i=1;i<=q;i++){
		string s;cin>>s;
		if(s[0]=='A'){
			++cnta;++edcnt;
			nn[cnta]=edcnt;
			ll u,v;cin>>u>>v>>s;
			reverse(s.begin(),s.end());
			EJZ lls=dwy;
			for(int j=0;j<16;j++) for(int k=j*64,p=0;p<64;k++,p++) if(s.size()>k&&s[k]=='1') lls.a[j]|=(1ull<<p);
			e[edcnt].u=u;e[edcnt].v=v;e[edcnt].tl=i;e[edcnt].tr=q;e[edcnt].w=lls;
		}
		else if(s[1]=='h'){
			ll k;
			cin>>k>>s;
			reverse(s.begin(),s.end());
			EJZ lls=dwy;
			for(int j=0;j<16;j++) for(int k=j*64,p=0;p<64;k++,p++) if(s.size()>k&&s[k]=='1') lls.a[j]|=(1ull<<p);
			++edcnt;
			int sdf=nn[k];
			e[nn[k]].tr=i-1;
			nn[k]=edcnt;
			e[edcnt].u=e[sdf].u;e[edcnt].v=e[sdf].v;e[edcnt].w=lls;e[edcnt].tl=i;e[edcnt].tr=q;
		}
		else{
			ll k;cin>>k;
			e[nn[k]].tr=i-1;
		}
	}
	vector<ll> atf;
	for(int i=1;i<=edcnt;i++) atf.push_back(i);
	solve(0,q+1,atf);
	for(int i=0;i<=q;i++){
		bool flag=false;
		for(int j=MAXN-1;j>=0;j--){
			bool x=get(ans[i],j);
			if(flag||x){
				flag=true;
				cout<<(x?'1':'0');
			}
		}
		if(!flag) cout<<'0';
		cout<<"\n";
	}
	return 0;
}