首先给出一个长度为2n的序列，我们定义一个值v，这个值是由如下计算方法得到的，首先将A序列的第2*i-1位和第2*i位(i=1,2,..,2n-1)进行OR操作得到新数列A'，然后再对A'序列操作，将A' 序列的第2*i位和第2*i-1位(i=1,2,...,2n-2)进行XOR操作得到A''，对A''按照第一次操作方式进行OR操作，因为序列长度为2n,所以显然进行n次操作之后就只剩下一个数字了此时这个数字就是v。
例如A={1，2，3，4}，第一次操作之后为{1|2=3，3|4=7}，第二次操作后，{3^7=4},所以v=4。
但是显然事情并没有那么简单，给出A序列后，还有m个操作，每个操作表示为“a b”，表示将A[a]改为b，之后再对A序列求v值。
输入第一行包含两个正整数n，m，分别表示A序列的长度为2^n,操作数量为m。（1<=n<=17,1<=m<=10^5）
输入第二行包含n个正整数，中间用空格隔开，表示A序列。（0<=ai<=2^30）
接下来有m行，每行包含两个正整数a，b，表示一次操作，即把A[a]变成b。(1<=a<=2^n, 0<=b<=2^30)
输出包含m行，第i行表示进行了第i次操作之后，A序列的v值。
2 4 1 2 3 4 1 4 3 4 1 3 1 3
1 2 7 7
#include <bits/stdc++.h>
using namespace std;
const int maxN=(1<<18)+2;
int tree[4*maxN+50],n,nums[maxN];
int build(int i,int l,int r){
if(l==r){
tree[i]=nums[l];
return 1;
}
else{
int mid=(l+r)/2,last;
last=build(2*i+1,l,mid);
last=build(2*i+2,mid+1,r);
if(last){
tree[i]=tree[2*i+1]|tree[2*i+2];
}
else{
tree[i]=tree[2*i+1]^tree[2*i+2];
}
return 1-last;
}
}
int update(int index,int value,int l,int r,int i){//返回值为1应该使用或，0则为异或
if(index<l || index>r){
return 0;
}
if(l==r && l==index){
tree[i]=value;
return 1;
}
int mid=(l+r)/2,last;
if(index>mid){
last=update(index,value,mid+1,r,2*i+2);
}
else{
last=update(index,value,l,mid,2*i+1);
}
if(last){
tree[i]=tree[2*i+1]|tree[2*i+2];
}
else{
tree[i]=tree[2*i+1]^tree[2*i+2];
}
return 1-last;
}
int main(){
int m,logn;
cin>>logn>>m;
n=pow(2,logn);
for (int i=0;i<n;i++){
scanf("%d",&nums[i]);
}
build(0,0,n-1);
cout<<endl;
//dfs(0,0,n-1);
cout<<endl;
int index,value;
for (int i=0;i<m;i++){
scanf("%d %d",&index,&value);
int j=index-1;
update(j,value,0,n-1,0);
cout<<tree[0]<<endl;
//update(j,nums[j],0,n-1,0);
}
} import java.util.Scanner;
public class Main {
static SegmentTree tree;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int len = (int)Math.pow(2, n);
int[] A = new int[len];
for(int i = 0; i < len; i++) A[i] = sc.nextInt();
// 对原始序列构建线段树
tree = new SegmentTree(A, len);
tree.buildTree(0, 0, len - 1);
// 对线段树进行更新操作O(mlogn)
for(int i = 0; i < m; i++){
int a = sc.nextInt() - 1;
int b = sc.nextInt();
tree.update(a, b, 0, len - 1, 0);
// 第一个元素就是所有值两两配对后只剩一个数的操作结果
System.out.println(tree.tree[0]);
}
}
}
class SegmentTree {
int[] data;
int[] tree;
public SegmentTree(int[] data, int n) {
this.data = data;
tree = new int[4*n];
}
public boolean buildTree(int treeIndex, int l, int r) {
if(l == r){
tree[treeIndex] = data[l];
// 递归到叶子节点，第一次使用或
return true;
}else{
int mid = (l + r) / 2;
boolean isOR;
// 左孩子根节点2i+1，对应区间为[l,mid]
isOR = buildTree(2*treeIndex + 1, l, mid);
// 左孩子根节点2i+2，对应区间为[mid+1,r]
isOR = buildTree(2*treeIndex + 2, mid + 1, r);
if(isOR){
// 使用或
tree[treeIndex] = tree[2*treeIndex + 1]|tree[2*treeIndex + 2];
}else{
// 使用异或
tree[treeIndex] = tree[2*treeIndex + 1]^tree[2*treeIndex + 2];
}
// 如果本轮是或操作，下一轮就是异或操作，反之亦然
return !isOR;
}
}
public boolean update(int index, int value, int l, int r, int i) {
if(index < l || index > r) return false;
if(l == r && l == index){
// 更新叶子节点的值
tree[i] = value;
return true;
}
// 自底向上更新非叶子节点的值
int mid = (l + r) / 2;
boolean isOR;
if(index > mid)
isOR = update(index, value, mid + 1, r, 2*i + 2);
else
isOR = update(index, value, l, mid, 2*i + 1);
if(isOR)
tree[i] = tree[2*i + 1]|tree[2*i + 2];
else
tree[i] = tree[2*i + 1]^tree[2*i + 2];
return !isOR;
}
} def main(): logn, m = map(int, input().strip().split()) n = 2 ** logn storeN = 2 ** (logn + 1) - 1 tree = [0] * storeN nums = list(map(int, input().strip().split())) def build(i, l, r): if l == r: tree[i] = nums[l] return 1 else: mid = (l + r) // 2 last = build(2 * i + 1, l, mid) last = build(2 * i + 2, mid + 1, r) if last: tree[i] = tree[2 * i + 1] | tree[2 * i + 2] else: tree[i] = tree[2 * i + 1] ^ tree[2 * i + 2] return 1 - last def update(index, value, l, r, i): if index < l&nbs***bsp;index > r: return 0 if l == r and l == index: tree[i] = value return 1 mid = (l + r) // 2 if index > mid: last = update(index, value, mid + 1, r, 2 * i + 2) else: last = update(index, value, l, mid, 2 * i + 1) if last: tree[i] = tree[2 * i + 1] | tree[2 * i + 2] else: tree[i] = tree[2 * i + 1] ^ tree[2 * i + 2] return 1 - last build(0, 0, n - 1) for i in range(m): index, value = map(int, input().strip().split()) j = index - 1 update(j, value, 0, n - 1, 0) print(tree[0]) if __name__ == '__main__': main()
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
