[Codeforces 339D] Xenia and Bit Operations
发布时间:2020-12-14 04:21:48 所属栏目:大数据 来源:网络整理
导读:[题目链接] ? ? ? ??https://codeforces.com/problemset/problem/339/D [算法] ? ? ? ? 线段树模拟即可 ? ? ? ? 时间复杂度 :O(MN) [代码] ? ? ? ? ? #includebits/stdc++.h using namespace std; #define MAXN 18 const int MAXS = 1 MAXN; int n,m; int a
[题目链接] ? ? ? ??https://codeforces.com/problemset/problem/339/D [算法] ? ? ? ? 线段树模拟即可 ? ? ? ? 时间复杂度 :O(MN) [代码] ? ? ? ? ? #include<bits/stdc++.h> using namespace std; #define MAXN 18 const int MAXS = 1 << MAXN; int n,m; int a[MAXS]; struct SegmentTree { struct Node { int l,r; int value,d; } Tree[MAXS << 2]; inline void update(int index) { if (Tree[index].d == 1) Tree[index].value = Tree[index << 1].value | Tree[index << 1 | 1].value; else Tree[index].value = Tree[index << 1].value ^ Tree[index << 1 | 1].value; } inline void build(int index,int l,int r) { Tree[index].l = l; Tree[index].r = r; if (l == r) { Tree[index].value = a[l]; Tree[index].d = 0; return; } int mid = (l + r) >> 1; build(index << 1,l,mid); build(index << 1 | 1,mid + 1,r); Tree[index].d = (Tree[index << 1].d + 1) % 2; update(index); } inline void modify(int index,int pos,int val) { if (Tree[index].l == Tree[index].r) { Tree[index].value = val; return; } int mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= pos) modify(index << 1,pos,val); else modify(index << 1 | 1,val); update(index); } inline int query() { return Tree[1].value; } } T; template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - ‘0‘; x *= f; } int main() { read(n); read(m); for (int i = 1; i <= (1 << n); i++) read(a[i]); T.build(1,1,(1 << n)); while (m--) { int x,y; read(x); read(y); T.modify(1,x,y); printf("%dn",T.query()); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |