尼玛这题出题人太JB NB了,乍一看以为线段树,仔细看看发现不是,查询时区间不连续
后来就搜索解题报告,才知道是并查集 ,但是又不知道咋个并,咋个查。。。ORZ,,,,蒟蒻,
题意:给出一个数值固定的数列,x0,x1,x2,……xn-1;
#include<cstdio> #include<string.h> #include<algorithm> #include<cmath> #include<vector> #include<map> using namespace std; const int N=23002; int n,val[N],father[N]; void init(int n) { for(int i=0;i<=n;i++) { val[i]=0; father[i]=i; } } int find(int x) { if(x==father[x]) { return x; } int tmp=find(father[x]); val[x]^=val[father[x]]; father[x]=tmp; return father[x]; } bool Union(int x,int y,int v) { int fx=find(x); int fy=find(y); if(fx==fy) { return v==(val[x]^val[y]); } if(fy==n) swap(fx,fy); val[fy]=val[x]^val[y]^v; father[fy]=fx; return true; } int main() {freopen("/home/kapop/pro/1.txt","r",stdin); freopen("/home/kapop/pro/2.txt","w",stdout); int Q; char op[12]; char str[11]; int x,y,v; int tt=1; int step=0; bool ok=true; while(~scanf("%d%d",&n,&Q)){ if(n+Q==0)break; printf("Case %d:\n",tt++);step=0; init(n); ok=true; while(Q--){ scanf("%s",op); if('I'==op[0]) {step++; gets(str); int cnt=sscanf(str,"%d %d %d",&x,&y,&v); if(cnt==2) { v=y;y=n; } if(!ok) continue; if(!Union(x,y,v)){ ok=false; printf("The first %d facts are conflicting.\n",step); } } else if('Q'==op[0]){ if(!ok) { int kk,ta; scanf("%d",&kk); while(kk--){ scanf("%d",&ta); } } else{ int nn,pp,ans=0; map<int ,int>M; bool mn=true; scanf("%d",&nn); for(int i=1;i<=nn;i++){ scanf("%d",&pp); if(!ok)continue; int yy=find(pp); ans^=val[pp]; M[yy]++; } if(!ok)continue; for(map<int ,int >::iterator it=M.begin();it!=M.end();it++) { if(it->second %2){ if(it->first != n){mn=false;break;} } } if(mn){ printf("%d\n",ans); } else{ printf("I don't know.\n"); } } } } } return 0; }