JZOJ5373【NOIP2017提高A组模拟9.17】信仰是为了虚无之人-白红宇

JZOJ5373【NOIP2017提高A组模拟9.17】信仰是为了虚无之人

阅读量：5235 次

发布时间：2019-06-14

本文共 1205 字，大约阅读时间需要 4 分钟。

题目

这里写图片描述

分析

我们发现，如果[l,r]的异或和为k是真要求，有且仅当不存在[l,i]和[i,r]两个区间的异或和不为k。

我们用带权并查集了维护这些，但是，由于区间不连续，我们将点权移到边上，对于区间[l,r]的点权异或和，变成[l,r+1]边权异或和。并查集合并时将大点连向小点，

最后通过并查集求异或点缀和，如果某个点没有限制，值为零。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           const int maxlongint=2147483647;const int mo=1e9+7;const int N=200005;using namespace std;int b[N*2][3],fa[N],v[N],n,m,czy,ans,tot,sum[N],la[N*2],ne[N*2],vv[N*2],to[N*2];int get(int x){ if(x==fa[x]) return x; int y=get(fa[x]); v[x]^=v[fa[x]]; return fa[x]=y;}int main(){ freopen("sanae.in","r",stdin); //freopen("sanae.out","w",stdout); scanf("%d%d%d",&n,&m,&czy); for(int i=1;i<=n+1;i++) fa[i]=i; int tot=0; for(int i=1,x,y,k;i<=m;i++) { scanf("%d%d%d",&x,&y,&k); x^=ans*czy,y^=ans*czy,k^=ans*czy; int xx=get(x),yy=get(y+1); if(xx>yy) swap(xx,yy); if(xx==yy) { if((v[x]^v[y+1])!=k) ans=0; else ans=1; } else { ans=1; fa[yy]=xx,v[yy]=k^v[x]^v[y+1]; } printf("%d\n",ans); } for(int i=2;i<=n+1;i++) { int j=get(i); if(i==j) sum[i]=sum[i-1]; else sum[i]=sum[j]^v[i]; if(i!=1) printf("%d\n",sum[i]^sum[i-1]); }}