codeforces 482B. Interesting Array【线段树区间更新】

矫情吗;* 2022-08-13 13:47 259阅读 0赞

题目:codeforces 482B. Interesting Array

题意:给你一个值n和m中操作,每种操作就是三个数 l ,r,val。就是区间l—-r上的与的值为val,最后问你原来的数组是多少?如果不存在输出no

分析:分析发现要满足所有的区间,而一个点上假如有多个区间的话,这个点的值就是所有区间或的值,因为只有这样才能满足所有区间的,把所有位上的1都保存下来了,那么可以发现用线段树来维护,但是那么怎么判断满不满足条件呢?可以也用线段树,更新了之后在整个维护一遍看看满不满足题意,如果满足的话就可以了。

AC代码:

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5. const int N = 110000;
  6. struct Node
  7. {
  8. int l,r;
  9. int val;
  10. };
  11. Node tree[10*N];
  12. void build(int o,int l,int r)
  13. {
  14. tree[o].l = l,tree[o].r = r;
  15. tree[o].val = 0;
  16. if(l==r)
  17. return ;
  18. int mid = (l+r)/2;
  19. build(o+o,l,mid);
  20. build(o+o+1,mid+1,r);
  21. }
  22. void update(int o,int l,int r,int val)
  23. {
  24. if(tree[o].l==l && tree[o].r==r)
  25. {
  26. tree[o].val|=val;
  27. return ;
  28. }
  29. int mid = (tree[o].l + tree[o].r)/2;
  30. if(mid>=r)
  31. update(o+o,l,r,val);
  32. else if(l>mid)
  33. update(o+o+1,l,r,val);
  34. else
  35. {
  36. update(o+o,l,mid,val);
  37. update(o+o+1,mid+1,r,val);
  38. }
  39. }
  40. int query(int o,int l,int r)
  41. {
  42. if(tree[o].l==l && tree[o].r==r)
  43. return tree[o].val;
  44. int mid = (tree[o].l + tree[o].r)/2;
  45. if(mid>=r)
  46. return query(o+o,l,r);
  47. else if(l>mid)
  48. return query(o+o+1,l,r);
  49. else
  50. {
  51. return query(o+o,l,mid)&query(o+o+1,mid+1,r);
  52. }
  53. }
  54. vector<int> ans;
  55. void solve(int o)
  56. {
  57. if(o!=1)
  58. tree[o].val |= tree[o/2].val;
  59. //printf("%d %d %d %d\n",o,tree[o].l,tree[o].r,tree[o].val);
  60. if(tree[o].l==tree[o].r){
  61. ans.push_back(tree[o].val);
  62. return ;
  63. }
  64. solve(o+o);
  65. solve(o+o+1);
  66. }
  67. Node a[N];
  68. int main()
  69. {
  70. //freopen("Input.txt","r",stdin);
  71. int n,m;
  72. scanf("%d%d",&n,&m);
  73. build(1,1,n);
  74. for(int i=0;i<m;i++)
  75. {
  76. scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
  77. update(1,a[i].l,a[i].r,a[i].val);
  78. }
  79. int ok=1;
  80. for(int i=0;i<m;i++)
  81. {
  82. if(query(1,a[i].l,a[i].r)!=a[i].val)
  83. {
  84. ok=0;
  85. break;
  86. }
  87. }
  88. solve(1);
  89. if(ok){
  90. puts("YES");
  91. for(int i=0;i<ans.size();i++)
  92. printf("%d%c",ans[i],i==n?'\n':' ');
  93. ans.clear();
  94. }
  95. else
  96. puts("NO");
  97. return 0;
  98. }

发表评论

表情:
评论列表 (有 0 条评论,259人围观)

还没有评论,来说两句吧...

相关阅读

    相关 线段区间更新

    线段树成段更新延迟标记理解 区间更新是指每次更新的时候更新的是一个区间里面的所有值,例如将区间\[l,r\]内的所有点都加或者减去一个数,或者替换成一个数字等等.因为区间更新