传送门
中文题。
思路：判断2个异或组成的数的集合的关系，就要利用到线性基的知识。如果1个线性基包含另一个线性基，那么另一个线性基里的任意元素一定能被这个线性基表示出来。其它的就是利用线段树维护线性基了。(不过我代码跑的速度有点慢~)
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int maxn=5e4+10; struct node{ long long d[65],cnt; ll p[65]; node() { memset(d,0,sizeof(d)); memset(p,0,sizeof(p)); cnt=0; } bool insert(long long val) { for (int i=60;i>=0;i--) if (val&(1ll<<i)) { if (!d[i]) { d[i]=val; break; } val^=d[i]; } return val>0;//val变成了0，那么说明x在线性基内。 } void rebuild() { for (int i=60;i>=0;i--) for (int j=i-1;j>=0;j--) if (d[i]&(1LL<<j)) d[i]^=d[j]; for (int i=0;i<=60;i++) if (d[i]) p[cnt++]=d[i]; } }a[maxn<<2]; node merge (node u,node v) { for(int i=60;i>=0;i--) { if(v.d[i]) { u.insert(v.d[i]); } } return u; } void build(int l,int r,int rt) { if(l==r) { ll tp; scanf("%lld",&tp); a[rt].insert(tp); return ; } int mid=(l+r)/2; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); a[rt]=merge(a[rt<<1],a[rt<<1|1]); } node query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return a[rt]; } node tt; int mid=(l+r)/2; if(L<=mid) tt=merge(tt,query(L,R,l,mid,rt<<1)); if(R>mid) tt=merge(tt,query(L,R,mid+1,r,rt<<1|1)); return tt; } void updata(int u,int l,int r,int rt,ll x) //更新 { if(l==r) { memset(a[rt].d,0,sizeof(a[rt].d)); a[rt].insert(x); return ; } int mid=(l+r)/2; if(u<=mid) updata(u,l,mid,rt<<1,x); else updata(u,mid+1,r,rt<<1|1,x); a[rt]=merge(a[rt<<1],a[rt<<1|1]); } int main() { node(); int n,m; scanf("%d%d",&n,&m); build(1,n,1); while(m--) { int op; scanf("%d",&op); if(op==1) { ll y; int x; scanf("%d%lld",&x,&y); updata(x,1,n,1,y); } else{ int l1,r1,l2,r2; scanf("%d%d%d%d",&l1,&r1,&l2,&r2); node s1=query(l1,r1,1,n,1); node s2=query(l2,r2,1,n,1); /* s1.rebuild(); for(int i=0;i<s1.cnt;i++) { cout<<s1.p[i]<<" "; } cout<<endl; s2.rebuild(); for(int i=0;i<s2.cnt;i++) { cout<<s2.p[i]<<" "; } cout<<endl; */ int t1=0,t2=0; for(int i=60;i>=0;i--) { if(s1.d[i]>0&&s2.insert(s1.d[i])==1) { t1=1; } if(s2.d[i]>0&&s1.insert(s2.d[i])==1) { t2=1; } } if(t1==0&&t2==0) printf("0\n"); else if(t1&&t2==0) printf("1\n"); else if(t2&&t1==0) printf("2\n"); else printf("3\n"); } } return 0; }
