经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
洛谷P5057 [CQOI2006]简单题(线段树)
来源:cnblogs  作者:自为风月马前卒  时间:2018/12/7 9:33:17  对本文有异议

题意

题目链接

Sol

紫色的线段树板子题??。。。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. using namespace std;
  5. const int MAXN = 1e6 + 10;
  6. inline int read() {
  7. char c = getchar(); int x = 0, f = 1;
  8. while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();}
  9. while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
  10. return x * f;
  11. }
  12. int N, M;
  13. #define ls k << 1
  14. #define rs k << 1 | 1
  15. struct Node {
  16. int l, r, w, f;
  17. }T[MAXN];
  18. void Build(int k, int ll, int rr) {
  19. T[k].l = ll; T[k].r = rr; T[k].w = -1; T[k].f = 0;
  20. if(ll == rr) {T[k].w = 0; return ;}
  21. int mid = (T[k].l + T[k].r) >> 1;
  22. Build(ls, ll, mid); Build(rs, mid + 1, rr);
  23. }
  24. void Reverse(int k, int ll, int rr) {
  25. if(ll <= T[k].l && T[k].r <= rr) {T[k].f ^= 1; return ;}
  26. int mid = (T[k].l + T[k].r) >> 1;
  27. if(ll <= mid) Reverse(ls, ll, rr);
  28. if(rr > mid) Reverse(rs, ll, rr);
  29. }
  30. int Query(int k, int pos) {
  31. int ans = T[k].f;
  32. if(T[k].l == T[k].r) return ans;
  33. int mid = (T[k].l + T[k].r) >> 1;
  34. if(pos <= mid) ans ^= Query(ls, pos);
  35. if(pos > mid) ans ^= Query(rs, pos);
  36. return ans;
  37. }
  38. int main() {
  39. N = read(); M = read();
  40. Build(1, 1, N);
  41. while(M--) {
  42. int opt = read();
  43. if(opt == 1) {
  44. int l = read(), r = read();
  45. Reverse(1, l, r);
  46. } else {
  47. printf("%d\n", Query(1, read()));
  48. }
  49. }
  50. return 0;
  51. }
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号