FZU-2105 Digits Count （两种标记成段更新）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了FZU-2105 Digits Count （两种标记成段更新），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2933字，纯文字阅读大概需要5分钟。
内容图文
题目大意：给n个0~15之间的数，有3种更新操作，1种询问操作。3种更新操作是：1、让某个闭区间的所有数字与一个0~15之间的数字进行逻辑与运算；2、让某个闭区间的所有数字与一个0~15之间的数字进行逻辑或运算；3、让某个闭区间的所有数字与一个0~15之间的数字进行异或运算。一种询问操作是询问某个闭区间的所有数字之和。
题目分析：所有的输入数字都是在0~15之间，可以二进制中的每一位建立线段树，建立四棵。3种更新操作实际上只有两种，即区间置位和区间反转。用两个懒惰标记，当进行区间置位更新的时候，要清除已经存在的反转标记，这样就能保证标记下传时两种标记下传的先后次序。
代码如下：
# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;
# define LL long long
const int N=1000000;
int n,m;
int a[N+5];
int tr[4][N*4+5];
int lazy[4][N*4+5];
int lazy_xor[4][N*4+5];
char com[5];
void pushDown(int id,int rt,int l,int r)
{
int mid=l+(r-l)/2;
if(lazy[id][rt]!=-1){
lazy_xor[id][rt<<1]=lazy_xor[id][rt<<1|1]=0;
lazy[id][rt<<1]=lazy[id][rt<<1|1]=lazy[id][rt];
tr[id][rt<<1]=lazy[id][rt]*(mid-l+1);
tr[id][rt<<1|1]=lazy[id][rt]*(r-mid);
lazy[id][rt]=-1;
}
int &q=lazy_xor[id][rt];
if(q==1){
lazy_xor[id][rt<<1]^=1;
lazy_xor[id][rt<<1|1]^=1;
tr[id][rt<<1]=mid-l+1-tr[id][rt<<1];
tr[id][rt<<1|1]=r-mid-tr[id][rt<<1|1];
q=0;
}
}
void pushUp(int id,int rt)
{
tr[id][rt]=tr[id][rt<<1]+tr[id][rt<<1|1];
}
void build(int id,int rt,int l,int r)
{
lazy[id][rt]=-1;
lazy_xor[id][rt]=0;
if(l==r){
if((a[r]&(1<<id))>0) tr[id][rt]=1;
else tr[id][rt]=0;
}else{
int mid=l+(r-l)/2;
build(id,rt<<1,l,mid);
build(id,rt<<1|1,mid+1,r);
pushUp(id,rt);
}
}
void update(int id,int rt,int l,int r,int L,int R,int x)
{
if(L<=l&&r<=R){
if(x==2){
if(lazy[id][rt]!=-1) lazy[id][rt]^=1;
else lazy_xor[id][rt]^=1;
tr[id][rt]=(r-l+1)-tr[id][rt];
}else{
lazy[id][rt]=x;
lazy_xor[id][rt]=0;
tr[id][rt]=x*(r-l+1);
}
}else{
pushDown(id,rt,l,r);
int mid=l+(r-l)/2;
if(L<=mid) update(id,rt<<1,l,mid,L,R,x);
if(R>mid) update(id,rt<<1|1,mid+1,r,L,R,x);
pushUp(id,rt);
}
}
LL query(int id,int rt,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return tr[id][rt];
pushDown(id,rt,l,r);
int mid=l+(r-l)/2;
LL res=0;
if(L<=mid) res+=query(id,rt<<1,l,mid,L,R);
if(R>mid) res+=query(id,rt<<1|1,mid+1,r,L,R);
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i) scanf("%d",a+i);
for(int i=0;i<4;++i)
build(i,1,0,n-1);
int o,b,c;
while(m--)
{
scanf("%s",com);
if(com[0]==‘S‘){
scanf("%d%d",&b,&c);
int ans=0;
for(int i=0;i<4;++i){
ans+=query(i,1,0,n-1,b,c)*(1<<i);
}
printf("%d\n",ans);
}else{
scanf("%d%d%d",&o,&b,&c);
if(com[0]==‘X‘){
for(int i=0;i<4;++i) if(o&(1<<i))
update(i,1,0,n-1,b,c,2);
}else if(com[0]==‘O‘){
for(int i=0;i<4;++i) if(o&(1<<i))
update(i,1,0,n-1,b,c,1);
}else if(com[0]==‘A‘){
for(int i=0;i<4;++i) if(!(o&(1<<i)))
update(i,1,0,n-1,b,c,0);
}
}
}
}
return 0;
}
原文：http://www.cnblogs.com/20143605--pcx/p/5552416.html
内容总结
以上是互联网集市为您收集整理的FZU-2105 Digits Count （两种标记成段更新）全部内容，希望文章能够帮你解决FZU-2105 Digits Count （两种标记成段更新）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。