首页 > 代码库 > codeforces 482B. Interesting Array【线段树区间更新】
codeforces 482B. Interesting Array【线段树区间更新】
题目:codeforces 482B. Interesting Array
题意:给你一个值n和m中操作,每种操作就是三个数 l ,r,val。就是区间l---r上的与的值为val,最后问你原来的数组是多少?如果不存在输出no
分析:分析发现要满足所有的区间,而一个点上假如有多个区间的话,这个点的值就是所有区间或的值,因为只有这样才能满足所有区间的,把所有位上的1都保存下来了,那么可以发现用线段树来维护,但是那么怎么判断满不满足条件呢?可以也用线段树,更新了之后在整个维护一遍看看满不满足题意,如果满足的话就可以了。
AC代码:
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int N = 110000; struct Node { int l,r; int val; }; Node tree[10*N]; void build(int o,int l,int r) { tree[o].l = l,tree[o].r = r; tree[o].val = 0; if(l==r) return ; int mid = (l+r)/2; build(o+o,l,mid); build(o+o+1,mid+1,r); } void update(int o,int l,int r,int val) { if(tree[o].l==l && tree[o].r==r) { tree[o].val|=val; return ; } int mid = (tree[o].l + tree[o].r)/2; if(mid>=r) update(o+o,l,r,val); else if(l>mid) update(o+o+1,l,r,val); else { update(o+o,l,mid,val); update(o+o+1,mid+1,r,val); } } int query(int o,int l,int r) { if(tree[o].l==l && tree[o].r==r) return tree[o].val; int mid = (tree[o].l + tree[o].r)/2; if(mid>=r) return query(o+o,l,r); else if(l>mid) return query(o+o+1,l,r); else { return query(o+o,l,mid)&query(o+o+1,mid+1,r); } } vector<int> ans; void solve(int o) { if(o!=1) tree[o].val |= tree[o/2].val; //printf("%d %d %d %d\n",o,tree[o].l,tree[o].r,tree[o].val); if(tree[o].l==tree[o].r){ ans.push_back(tree[o].val); return ; } solve(o+o); solve(o+o+1); } Node a[N]; int main() { //freopen("Input.txt","r",stdin); int n,m; scanf("%d%d",&n,&m); build(1,1,n); for(int i=0;i<m;i++) { scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val); update(1,a[i].l,a[i].r,a[i].val); } int ok=1; for(int i=0;i<m;i++) { if(query(1,a[i].l,a[i].r)!=a[i].val) { ok=0; break; } } solve(1); if(ok){ puts("YES"); for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i==n?'\n':' '); ans.clear(); } else puts("NO"); return 0; }
codeforces 482B. Interesting Array【线段树区间更新】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。