CodeForces 339D Xenia and Bit Operations (线段树)
and Codeforces 线段 bit operations
2023-09-11 14:17:19 时间
题意:给定 2的 n 次方个数,对这些数两个两个的进行或运算,然后会减少一半的数,然后再进行异或运算,又少了一半,然后再进行或运算,再进行异或,不断重复,到最后只剩下一个数,要输出这个数,然后有 m 个询问,
每个询问有 p 和 b,要求把第 p 个数改成 b,再这样运算,输出结果。
析:这个题是不是很像线段树,不过这个题不是随机询问哪个区间,区间是固定的,这样也就简单了很多,就省下了一个query函数,再就是线段树是从上到下的,所以我们要分好到底是异或还是或,然后就很简单了,
其实这个题也可以这样想,也是先构造一棵树,然后再考虑从下到上进行变,因为要改变值,所以先把最下面的改掉,然后再更新上去,这样次数比线段树少,比它更快一点,其实原理也是一样的。
代码如下:
线段树:
#include <bits/stdc++.h> #define lson l,m,rt<<1,!ok #define rson m+1,r,rt<<1|1,!ok using namespace std; const int maxn = (1 << 17) + 5; int sum[maxn<<2]; void pushup(int rt, bool ok){ if(ok) sum[rt] = sum[rt<<1] | sum[rt<<1|1]; else sum[rt] = sum[rt<<1] ^ sum[rt<<1|1]; } void build(int l, int r, int rt, bool ok){ if(l == r){ scanf("%d", &sum[rt]); return ; } int m = (l+r) >> 1; build(lson); build(rson); pushup(rt, ok); } void update(int p, int b, int l, int r, int rt, bool ok){ if(l == r){ sum[rt] = b; return ; } int m = (l+r) >> 1; if(p <= m) update(p, b, lson); else update(p, b, rson); pushup(rt, ok); } int main(){ int num, mm; cin >> num >> mm; int n = (1 << num); bool ok = (num & 1); build(1, n, 1, ok); while(mm--){ int p, b; scanf("%d %d", &p, &b); update(p, b, 1, n, 1, ok); printf("%d\n", sum[1]); } return 0; }
另一种:
#include <bits/stdc++.h> using namespace std; const int maxn = (1 << 18) + 5; int a[maxn]; int num; int main(){ int n, m; cin >> n >> m; num = 1 << n; for(int i = 0; i < num; ++i) scanf("%d", &a[i+num]);//构造一棵树 int cnt = 0; int t = num; while(t){//把所有的值算一下 t >>= 1; for(int i = 0; i < t; ++i) if(cnt & 1) a[t+i] = a[(t+i)<<1] ^ a[(t+i)<<1|1]; else a[t+i] = a[(t+i)<<1] | a[(t+i)<<1|1]; ++cnt;//控制是或还是异或 } while(m--){ int p, b; scanf("%d %d", &p, &b); cnt = 0; p += num-1; a[p] = b; while(p){//从下到上更新 p >>= 1; if(cnt & 1) a[p] = a[p<<1] ^ a[p<<1|1]; else a[p] = a[p<<1] | a[p<<1|1]; ++cnt; } printf("%d\n", a[1]); } return 0; }
相关文章
- Codeforces Round #837 (Div. 2) C. Hossam and Trainees
- The Kernel Newbie Corner: Kernel and Module Debugging with gdb
- JavaScript----Performance Tool and Process
- CodeForces 785D Anton and School - 2 (组合数学)
- CodeForces 743A Vladik and flights (水题)
- CodeForces 712C Memory and De-Evolution (贪心+暴力)
- CodeForces 288A Polo the Penguin and Strings (水题)
- CodeForces 518B Tanya and Postcard (题意,水题)
- use ECharts with Angular 2 and TypeScript
- SAP MM: Change of material moving average price after goods receipt and invoice verification posting for PO
- Android中关于在onDrow或者onMeasure中创建对象提示Avoid object allocations during draw/layout operations (preallocate and reuse instead) 问题
- Unity Tutorial : VR, Oculus Avatar and Grabbing Object setup IN 5 MINUTES
- On Data Sharing Strategy for Decentralized Collaborative Visual-Inertial Simultaneous Localization and Mapping
- Hierarchy and examples of programming languages grouped by concepts --编程语言分类
- 【CodeForces 577C】Vasya and Petya’s Game
- 【CodeForces 613A】Peter and Snow Blower
- Codeforces Round #277.5 (Div. 2)C——Given Length and Sum of Digits...
- Codeforces 441 B. Valera and Fruits
- [LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal 由先序和后序遍历建立二叉树