首页 > 代码库 > Codeforces 242E. XOR on Segment
Codeforces 242E. XOR on Segment
题目大意：
给出一个序列，有两种操作，一种是计算l到r的和，另一种是让l到r的数全部和x做异或运算。
做法：
很显然直接暴力是不可能的（但是这题刚刚出来的时候，很多人用暴力水过去了，后来加强的数据吧），又是两种操作，又想到了线段树。。但是这并不简单，异或操作该怎么处理？
异或是一种位运算，如果x的第j位是1，那么说明l到r的每个数的第j位都要反转，（0^1=1,1^1=0）,如果是0，那么不变。既然是位运算，那么可不可以将每一位作为线段树单独维护呢？
好像可以呢！异或操作的话，相当于是一种区间操作，只需要将l到r的某些位进行反转操作不就行了吗？反转操作什么的，打上lazy tag不就OK啦，求和操作也可以计算出l到r的每一位上有多少个1来算出最后的和。
好，那么理一下思路，首先确定建立多少个线段树，数的范围是10^6，也就是说，我们最多只需要建立20个线段树即可，再写好线段树的bulid，update，query三个函数。每个节点上需要维护两个值，一个是该区间有多少个1（用于求和），一个是该区间是否反转（lazy tag）。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100010
#define L(x) (x)<<1
#define R(x) (x)<<1|1
using namespace std;
struct node
{
int l,r,cnt,lazy;
node(long long ll,long long rr,long long c,long long la)
{
l=ll,r=rr,cnt=c,lazy=la;
}
node()
{
l=r=cnt=lazy=0;
}
}p[20][N*4];
long long a[N][20],num[N],two[22];
long long bulid(long long id,long long l,long long r,long long na)
{
if(l==r){p[na][id]=node(l,r,a[l][na],0);return a[l][na];}
long long mid=(l+r)/2;
long long cur=bulid(L(id),l,mid,na)+bulid(R(id),mid+1,r,na);
p[na][id]=node(l,r,cur,0);
return cur;
}
void revers(long long id,long long l,long long r,long long na)
{
if(p[na][id].l==l && p[na][id].r==r)
{
p[na][id].lazy=1-p[na][id].lazy;
p[na][id].cnt=p[na][id].r-p[na][id].l+1-p[na][id].cnt;
return ;
}
if(p[na][id].lazy)//lazy tag 下放
{
p[na][id].lazy=0;
p[na][L(id)].lazy=1-p[na][L(id)].lazy;
p[na][R(id)].lazy=1-p[na][R(id)].lazy;
p[na][L(id)].cnt=p[na][L(id)].r-p[na][L(id)].l+1-p[na][L(id)].cnt;
p[na][R(id)].cnt=p[na][R(id)].r-p[na][R(id)].l+1-p[na][R(id)].cnt;
}
long long mid=(p[na][id].l+p[na][id].r)/2;
if(mid<l) revers(R(id),l,r,na);
else if(mid>=r) revers(L(id),l,r,na);
else revers(L(id),l,mid,na),revers(R(id),mid+1,r,na);
p[na][id].cnt=p[na][L(id)].cnt+p[na][R(id)].cnt;
}
long long query(long long id,long long l,long long r,long long na)
{
if(p[na][id].l==l && p[na][id].r==r) return p[na][id].cnt;
if(p[na][id].lazy)
{
p[na][id].lazy=0;
p[na][L(id)].lazy=1-p[na][L(id)].lazy;
p[na][R(id)].lazy=1-p[na][R(id)].lazy;
p[na][L(id)].cnt=p[na][L(id)].r-p[na][L(id)].l+1-p[na][L(id)].cnt;
p[na][R(id)].cnt=p[na][R(id)].r-p[na][R(id)].l+1-p[na][R(id)].cnt;
}
long long mid=(p[na][id].l+p[na][id].r)/2;
if(mid>=r) return query(L(id),l,r,na);
else if(mid<l) return query(R(id),l,r,na);
else return query(L(id),l,mid,na)+query(R(id),mid+1,r,na);
}
int main()
{
two[0]=1;
for(long long i=1;i<21;i++) two[i]=two[i-1]*2;
long long n;
scanf("%I64d",&n);
for(long long i=1;i<=n;i++)
{
scanf("%I64d",&num[i]);
long long j=0;
while(num[i]>0)
{
a[i][j++]=num[i]&1;
num[i]>>=1;
}
}
for(long long i=0;i<20;i++)
bulid(1,1,n,i);
long long m;
scanf("%I64d",&m);
while(m--)
{
long long ty;
scanf("%I64d",&ty);
if(ty==1)
{
long long a,b;
scanf("%I64d%I64d",&a,&b);
long long cur=0;
for(long long i=0;i<20;i++)
cur+=query(1,a,b,i)*two[i];
cout<<cur<<endl;
}
else
{
long long a,b,x;
scanf("%I64d%I64d%I64d",&a,&b,&x);
for(long long i=0;i<20 && x;i++,x>>=1)
{
if(x&1) revers(1,a,b,i);
}
}
}
return 0;
}Codeforces 242E. XOR on Segment
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。