CF Xenia and Bit Operations
题目描述：给你2^n个数a1,a2,a3…… 循环执行 第一步a1|a2 ,a3^a3
第二步将第一步得到的数执行 a[1]^a[2]…… 然后在执行第一步知道只剩下一个数，输出结果
基于上述的问题还有q次询问每次给你index，value表示将第index位的值替换为value 然后输出结果
分析： 显然是RMQ（区间查询） 借这个题顺便分析下树状数组何线段树的区别：树状数组的功能线段树都能完成，这不用说，那么线段树的功能有哪些是树状数组不能完成的？
对于线段树 update 是个回溯的过程所以就是想办法如何从两个子节点得到父节点的信息，对两个节点一起操作或者分开操作都行
而树状数组 的update是对于已知的结构由一个节点去推导父节点的信息，也就是不支持同时对两个节点的操作
ac代码：
#include<bits/stdc++.h>
using namespace std;
const int MAX=3e5;
int tree[4*MAX];
int a[MAX];
int index,value,flag1;
void build(int l,int r,int root,int flag){
if(l==r){
tree[root]=a[l];
flag1=flag;
return ;
}
int mid=(l+r)>>1;
build(l,mid,root<<1,flag^1);
build(mid+1,r,root<<1|1,flag^1);
if(flag1!=flag)tree[root]=tree[root<<1|1]|tree[root<<1];
else tree[root]=tree[root<<1|1]^tree[root<<1];
}
void update(int l,int r,int root,int flag){
if(l==r){
tree[root]=value;
flag1=flag;
return ;
}
int mid=(l+r)>>1;
if(index<=mid){
update(l,mid,root<<1,flag^1);
}
else {
update(mid+1,r,root<<1|1,flag^1);
}
if(flag1!=flag)tree[root]=tree[root<<1|1]|tree[root<<1];
else tree[root]=tree[root<<1|1]^tree[root<<1];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=(1<<n);i++){
cin>>a[i];
}
build(1,1<<n,1,0);
while(m--){
cin>>index>>value;
update(1,1<<n,1,0);
cout<<tree[1]<<endl;
}
}
查看12道真题和解析
