Codeforces Round #197 (Div. 2) D. Xenia and Bit Operations

2024-05-14 12:32

本文主要是介绍Codeforces Round #197 (Div. 2) D. Xenia and Bit Operations,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

D. Xenia and Bit Operations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Xenia the beginner programmer has a sequence a, consisting of 2n non-negative integers: a1, a2, ..., a2n. Xenia is currently studying bit operations. To better understand how they work, Xenia decided to calculate some value v for a.

Namely, it takes several iterations to calculate value v. At the first iteration, Xenia writes a new sequence a1 or a2, a3 or a4, ..., a2n - 1 or a2n, consisting of 2n - 1 elements. In other words, she writes down the bit-wise OR of adjacent elements of sequence a. At the second iteration, Xenia writes the bitwise exclusive OR of adjacent elements of the sequence obtained after the first iteration. At the third iteration Xenia writes the bitwise OR of the adjacent elements of the sequence obtained after the second iteration. And so on; the operations of bitwise exclusive OR and bitwise OR alternate. In the end, she obtains a sequence consisting of one element, and that element is v.

Let's consider an example. Suppose that sequence a = (1, 2, 3, 4). Then let's write down all the transformations (1, 2, 3, 4)  → (1 or 2 = 3, 3 or 4 = 7)  →  (3 xor 7 = 4). The result is v = 4.

You are given Xenia's initial sequence. But to calculate value v for a given sequence would be too easy, so you are given additional mqueries. Each query is a pair of integers p, b. Query p, b means that you need to perform the assignment ap = b. After each query, you need to print the new value v for the new sequence a.

Input

The first line contains two integers n and m (1 ≤ n ≤ 17, 1 ≤ m ≤ 105). The next line contains 2n integers a1, a2, ..., a2n (0 ≤ ai < 230). Each of the next m lines contains queries. The i-th line contains integers pi, bi (1 ≤ pi ≤ 2n, 0 ≤ bi < 230) — the i-th query.

Output

Print m integers — the i-th integer denotes value v for sequence a after the i-th query.

Sample test(s)
input
2 4
1 6 3 5
1 4
3 4
1 2
1 2
output
1
3
3
3
Note

For more information on the bit operations, you can follow this link: http://en.wikipedia.org/wiki/Bitwise_operati

简单线段树,也就是单点更新,这题要注意,分n为奇偶两种情况!

#include <iostream>
#include <stdio.h>
#include <string.h>
#define lson (num<<1)
#define rson (num<<1|1)
using namespace std;
#define MAXN 200000
__int64 l[20*MAXN];
int t;
void build(int num,int s,int e,int f)
{if(s>=e){scanf("%I64d",&l[num]);return ;}int mid=(s+e)>>1;build(lson,s,mid,f+1);build(rson,mid+1,e,f+1);if(t){if(f&1)l[num]=l[lson]|l[rson];elsel[num]=l[lson]^l[rson];}else{if(f&1)l[num]=l[lson]^l[rson];elsel[num]=l[lson]|l[rson];}
}
void update(int num,int s,int e,int pos,__int64 color,int f)
{if(s>=e){l[num]=color;return ;}int mid=(s+e)>>1;if(pos<=mid)update(lson,s,mid,pos,color,f+1);else if(pos>mid)update(rson,mid+1,e,pos,color,f+1);if(t){if(f&1)l[num]=l[lson]|l[rson];elsel[num]=l[lson]^l[rson];}else{if(f&1)l[num]=l[lson]^l[rson];elsel[num]=l[lson]|l[rson];}
}
int main()
{int n,m,i;while(scanf("%d%d",&n,&m)!=EOF){if(n&1)t=0;elset=1;n=1<<n;build(1,1,n,0);for(i=0;i<m;i++){int pos;__int64 num;scanf("%d%I64d",&pos,&num);update(1,1,n,pos,num,0);printf("%I64d\n",l[1]);}}return 0;
}


这篇关于Codeforces Round #197 (Div. 2) D. Xenia and Bit Operations的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/988749

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

[论文笔记]LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale

引言 今天带来第一篇量化论文LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale笔记。 为了简单,下文中以翻译的口吻记录,比如替换"作者"为"我们"。 大语言模型已被广泛采用,但推理时需要大量的GPU内存。我们开发了一种Int8矩阵乘法的过程,用于Transformer中的前馈和注意力投影层,这可以将推理所需

创建一个大的DIV,里面的包含两个DIV是可以自由移动

创建一个大的DIV,里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

CF#271 (Div. 2) D.(dp)

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/474/problem/D We s