codeforces 242E - XOR on Segment (线段树 按位数建树)
4 seconds
256 megabytes
standard input
standard output
You've got an array a, consisting of n integers a1, a2, ..., an. You are allowed to perform two operations on this array:
- Calculate the sum of current array elements on the segment [l, r], that is, count value al + al + 1 + ... + ar.
- Apply the xor operation with a given number x to each array element on the segment [l, r], that is, execute . This operation changes exactly r - l + 1 array elements.
Expression means applying bitwise xor operation to numbers x and y. The given operation exists in all modern programming languages, for example in language C++ and Java it is marked as "^", in Pascal — as "xor".
You've got a list of m operations of the indicated type. Your task is to perform all given operations, for each sum query you should print the result you get.
The first line contains integer n (1 ≤ n ≤ 105) — the size of the array. The second line contains space-separated integers a1, a2, ..., an(0 ≤ ai ≤ 106) — the original array.
The third line contains integer m (1 ≤ m ≤ 5·104) — the number of operations with the array. The i-th of the following m lines first contains an integer ti (1 ≤ ti ≤ 2) — the type of the i-th query. If ti = 1, then this is the query of the sum, if ti = 2, then this is the query to change array elements. If the i-th operation is of type 1, then next follow two integers li, ri (1 ≤ li ≤ ri ≤ n). If the i-th operation is of type 2, then next follow three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106). The numbers on the lines are separated by single spaces.
For each query of type 1 print in a single line the sum of numbers on the given segment. Print the answers to the queries in the order in which the queries go in the input.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams, or the %I64dspecifier.
5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3
26
22
0
34
11
6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3
38
28
题意;
两个操作:
1.输出区间l,r的和
2.让区间l,r每个数异或x
思路:
把数拆成二进制,对每一位建一棵线段树,记录每个数这一位是否为1,然后求一段区间的和就是这些线段树上这一段区间1的个数乘上2的位数-1次方,异或一个数x的话,我们将x拆成二进制,如果x的某一位为1的话那么就是对这段区间所有数的这一位都要变化,这一位线段树上直接区间异或标记就好了。
实现代码:
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid int m = (l + r) >> 1
#define ll long long
const int M = 1e5 + ; int sum[M<<][],lazy[M<<][],a[M],bit[]; void pushup(int rt){
for(int i = ;i <= ;i ++)
sum[rt][i] = sum[rt<<][i] + sum[rt<<|][i];
} void pushdown(int l,int r,int rt){
for(int i = ;i <= ;i ++)
if(lazy[rt][i]){
mid;
sum[rt<<][i] = m-l+-sum[rt<<][i];
sum[rt<<|][i] = r-m-sum[rt<<|][i];
lazy[rt<<][i] ^= lazy[rt][i];
lazy[rt<<|][i] ^= lazy[rt][i];
lazy[rt][i] = ;
}
} void build(int l,int r,int rt){
if(l == r){
int x = a[l],cnt = ;
while(x){
sum[rt][cnt++] = x%;
x = x/;
}
return;
}
mid;
build(lson); build(rson);
pushup(rt);
} void update(int L,int R,int x,int l,int r,int rt){
if(L <= l&&R >= r){
for(int i = ;i <= ;i ++){
if(x&(<<(i-))){
sum[rt][i] = r-l+-sum[rt][i];
lazy[rt][i] ^= ;
}
}
return ;
}
pushdown(l,r,rt);
mid;
if(L <= m) update(L,R,x,lson);
if(R > m) update(L,R,x,rson);
pushup(rt);
} ll query(int L,int R,int l,int r,int rt){
if(L <= l&&R >= r){
ll cnt = ;
for(int i = ;i <= ;i ++){
cnt += 1LL*sum[rt][i]*bit[i];
}
return cnt;
}
pushdown(l,r,rt);
mid; ll ret = ;
if(L <= m) ret += query(L,R,lson);
if(R > m) ret += query(L,R,rson);
return ret;
} int main(){
int n,q,l,r,x,op;
bit[] = ;
for(int i = ;i <= ;i ++)
bit[i] = bit[i-]*;
while(scanf("%d",&n)!=EOF){
for(int i = ;i <= n;i ++)
scanf("%d",&a[i]);
build(,n,);
scanf("%d",&q);
while(q--){
scanf("%d",&op);
if(op == ){
scanf("%d%d",&l,&r);
printf("%lld\n",query(l,r,,n,));
}
else{
scanf("%d%d%d",&l,&r,&x);
update(l,r,x,,n,);
}
}
}
return ;
}
最新文章
- JS详细教程(下)
- Servlet处理get请求时的中文乱码问题
- 用定时器令P0(或其它IO口)产生多路方波
- grunt安装_
- 了解oracle数据库的情况
- import了sun开头的类,虽然它在代码里压根就没派上用处!但是必须得引用!
- CSS控制 table 的 cellpadding,cellspacing
- power desinger 学习笔记<;六>;
- 轮值CEO胡厚崑:到2025年所有的企业都将用到云(云的2.0时代,会有几千朵云几万朵云升起来,这将产生不同的技术模式、商业模式、思维模式)
- Windbg简单介绍
- Directed Roads
- UESTC 771 最大容积(前缀后缀和)
- Openstack EOL 版本离线安装源
- 显示Linux进程打开了哪些文件? 用lsof命令
- C程序运行时的内存分布
- Code Pages
- 十、 持久层框架(MyBatis)
- oracle第一天笔记
- mysql load数据第一列丢失
- day27 python学习 logging