Sol

奶龙题，区间异或等价转化为前缀和的两个点异或，由于异或操作很好的性质直接带权并查集一下，能判断区间和当且仅当前缀和对应端点在同一连通块，直接查到根的异或和异或一下即可。

详细解释一部分：

不难发现，原先应当在并查集上查二者的路径的异或和，但是直接全部查到根也无妨，重合的部分会抵消掉。
使用并查集的正确性显然：两个区间端点重合，若二者不重叠，他们的并可求；若二者重叠，他们的对称差可求。并且由于是异或操作，所以很方便处理信息传递，无脑异或就行。

更多细节就详见代码吧，关于带权并查集的详细实现可以参阅相应模板题。

Code

CPP

const int N=4e5+5;

int q,n;
map<int,int> id;

int fa[N],rk[N],vl[N];
pii find(int x){int res=0;while(x!=fa[x])res^=vl[x],x=fa[x];return {x,res};}
void merge(int a,int b,int c){
	auto [x,vx]=find(a);auto [y,vy]=find(b);
	if(x==y)return;
	if(rk[x]>rk[y])swap(x,y),swap(vx,vy);
	c^=vx^vy;
	// cerr<<x<<"--->"<<y<<" "<<c<<"\n";
	fa[x]=y,rk[y]+=rk[x];vl[x]=c;
}
bool same(int a,int b){
	auto [x,vx]=find(a);auto [y,vy]=find(b);
	return x==y;
}

inline void Main(){
	cin>>q;
	int ans=0;
	rep(i,1,q){
		int t;cin>>t;
		if(t==1){
			int l,r,x;cin>>l>>r>>x;
			l^=ans,r^=ans,x^=ans;
			if(l>r)swap(l,r);
			if(!id[l-1])id[l-1]=++n,fa[n]=n,rk[n]=1;
			if(!id[r])id[r]=++n,fa[n]=n,rk[n]=1;
			merge(id[l-1],id[r],x);
		}else{
			int l,r;cin>>l>>r;
			l^=ans,r^=ans;
			if(l>r)swap(l,r);
			if(!id[l-1]||!id[r]||!same(id[l-1],id[r])){
				put(-1);
				ans=1;
			}else{
				ans=find(id[l-1]).sec,ans^=find(id[r]).sec;
				put(ans);
			}
		}
	}
}

题解：CF1044D Deduction Queries

文章操作

Sol

Code

相关推荐

评论

题解：CF1044D Deduction Queries