题解：CF1044D Deduction Queries

LastKismet · 2025-11-20 22:00:28 · 题解

Sol

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

详细解释一部分：

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

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

Code

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);
            }
        }
    }
}