CodeForces 242E - XOR on Segment 二维线段树？

CodeForces 242E - XOR on Segment 二维线段树？

今天练习赛的题....又是线段树的变换..拿到题我就敲了个点更新区间查询的..果断超时...然后想到了可以将每个数与合表示成不进位的二进制数..这样就可以区间进行更新了..比赛的时候写搓了..刚重写了一遍过~~

为了表示每位的二进制数...线段树开成二维的...第一维老样子~记是树中哪个点..第二维记当前段之和的不进位二进制数...因为最多到10^5...也就是不会超过2^20...第二维开个20就够了....

区间更新如:   3 3    这段全xor 3...3+3的不进位二进制数为(2,2)...xor 3,3的二进制为(1,1)..将x二进制为1的改为len-原来的...那么(2-2,2-2)=0

2 4    这段全xor 3...2+4的不进位二进制数为(1,1,0).....将x二进制为1的改为len-原来的..那么(1,2-1,2-0)=(1,1,2)=2+2+4=8

不知道这货是不是叫二维线段树.....二维线段树应该是树中有树吧..也就是第一颗树的每个节点又是线段树....

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 100005using namespace std; struct node{ int a[22];};int sum[MAXN<<2][22],col[MAXN<<2][22];ll h[22];void PushDown(int len,int now){ int i; for (i=0;i<20;i++) if (col[now][i]) { sum[now<<1][i]=(len-(len>>1))-sum[now<<1][i]; sum[(now<<1)|1][i]=(len>>1)-sum[(now<<1)|1][i]; col[now<<1][i]=1-col[now<<1][i]; col[(now<<1)|1][i]=1-col[(now<<1)|1][i]; } for (i=0;i<20;i++) col[now][i]=0; return;}void update(int L,int R,int x,int l,int r,int now){ int i; if (L<=l && R>=r) { for (i=0;i<20;i++) if (x&(1<>1; if (L<=mid) update(L,R,x,l,mid,now<<1); if (R>mid) update(L,R,x,mid+1,r,(now<<1)|1); for (i=0;i<20;i++) sum[now][i]=sum[now<<1][i]+sum[(now<<1)|1][i]; return;}node query(int L,int R,int l,int r,int now){ int i; node h; memset(h.a,0,sizeof(h.a)); if (L<=l && R>=r) { for (i=0;i<20;i++) h.a[i]=sum[now][i]; return h; } PushDown(r-l+1,now); int mid=(l+r)>>1; if (L<=mid) { node p=query(L,R,l,mid,now<<1); for (i=0;i<20;i++) h.a[i]+=p.a[i]; } if (R>mid) { node p=query(L,R,mid+1,r,(now<<1)|1); for (i=0;i<20;i++) h.a[i]+=p.a[i]; } return h;}int main(){ int i,n,m; while (~scanf("%d",&n)) { memset(sum,0,sizeof(sum)); memset(col,0,sizeof(col)); for (i=1;i<=n;i++) { int x; scanf("%d",&x); update(i,i,x,1,n,1); } scanf("%d",&m); while (m--) { int tp,l,r; scanf("%d%d%d",&tp,&l,&r); if (tp==1) { ll ans,x; node h=query(l,r,1,n,1); ans=0,x=1; for (i=0;i<20;i++) { ans+=x*h.a[i]; x*=2; } printf("%I64d\n",ans); }else { int x; scanf("%d",&x); update(l,r,x,1,n,1); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。