首页 > 代码库 > FZU 2105 Digits Count（按位维护线段树）
FZU 2105 Digits Count（按位维护线段树）
【题目链接】 http://acm.fzu.edu.cn/problem.php?pid=2105
【题目大意】
给出一个序列，数字均小于16，为正数，每次区间操作可以使得
1. [l,r]区间and一个数
2. [l,r]区间or一个数
3. [l,r]区间xor一个数
4. [l,r]区间查询和
操作数均为小于16的非负整数
【题解】
由于操作数很小，因此我们可以按位维护四棵线段树，表示二进制中的第i位，
对于and操作，只有当and的当前位为0时才对区间有影响，效果是将区间全部变为0，
对于or和xor操作，当前位为1的时候才对区间有影响，
因为and和or是全区间变化为同一个值，因此区间和会变为全区间或者0，
那么and和or的变化只需要看父区间的值来决定子区间的变化而不需要标记传递
对于xor操作，相当于区间01翻转，用一个标记记录翻转次数即可，
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int N=1000010;int T[4][N<<2],tag[4][N<<2],a[N];void up(int k,int x){T[k][x]=T[k][x<<1]+T[k][x<<1|1];}void pb(int k,int x,int l,int r){ int mid=(l+r)>>1; if(T[k][x]==r-l+1){T[k][x<<1]=mid-l+1;T[k][x<<1|1]=r-mid;} if(!T[k][x]){T[k][x<<1]=T[k][x<<1|1]=0;} if(tag[k][x]){ tag[k][x]^=1; if(T[k][x]!=r-l+1&&T[k][x]){ T[k][x<<1]=mid-l+1-T[k][x<<1]; T[k][x<<1|1]=r-mid-T[k][x<<1|1]; }tag[k][x<<1]^=1;tag[k][x<<1|1]^=1; }}void build(int k,int x,int l,int r){ int mid=(l+r)>>1; tag[k][x]=0; if(l==r){T[k][x]=(a[l]>>k)&1;return;} build(k,x<<1,l,mid);build(k,x<<1|1,mid+1,r); up(k,x);}void update(int k,int x,int l,int r,int L,int R,char op){ int mid=(l+r)>>1; if(L<=l&&r<=R){ if(op==‘A‘)T[k][x]=0; if(op==‘O‘)T[k][x]=r-l+1; if(op==‘X‘)T[k][x]=(r-l+1)-T[k][x],tag[k][x]^=1; return; }pb(k,x,l,r); if(L<=mid)update(k,x<<1,l,mid,L,R,op); if(mid+1<=R)update(k,x<<1|1,mid+1,r,L,R,op); up(k,x);}int query(int k,int x,int l,int r,int L,int R){ int mid=(l+r)>>1; if(L<=l&&r<=R)return T[k][x]; pb(k,x,l,r); int res=0; if(L<=mid)res+=query(k,x<<1,l,mid,L,R); if(mid+1<=R)res+=query(k,x<<1|1,mid+1,r,L,R); return res;}int Cas,n,m;char op[10];int main(){ scanf("%d",&Cas); while(Cas--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=0;i<4;i++)build(i,1,1,n); while(m--){ scanf("%s",op); if(op[0]==‘S‘){ int l,r,ans=0; scanf("%d%d",&l,&r); l++;r++; for(int i=0;i<4;i++)ans+=query(i,1,1,n,l,r)*(1<<i); printf("%d\n",ans); }else{ int l,r,x; scanf("%d%d%d",&x,&l,&r); l++,r++; for(int i=0;i<4;i++)if((op[0]==‘A‘)^((x>>i)&1))update(i,1,1,n,l,r,op[0]); } } }return 0;}FZU 2105 Digits Count（按位维护线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。