Codeforces 482B Interesting Array(线段树区间更新)

题目链接 Interesting Array

区间更新。然后对于每一个约数重新求一遍区间的&值,不符合就跳出。

 #include <bits/stdc++.h>

 using namespace std;

 #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define lson i << 1, L, mid
#define rson i << 1 | 1, mid + 1, R const int N = ; struct node{
int l, r, val;
} a[N]; int tree[N << ], ans[N];
int n, m;
int ret = ; void update(int i, int L, int R, int l, int r, int val){
if (L == l && R == r){ tree[i] |= val; return ;}
int mid = (L + R) >> ;
if (r <= mid) update(lson, l, r, val);
else if (l > mid) update(rson, l, r, val);
else{
update(lson, l, mid, val);
update(rson, mid + , r, val);
}
} int query(int i, int L, int R, int l, int r){
if (L == l && R == r) return tree[i];
int mid = (L + R) >> ;
if (r <= mid) return query(lson, l, r);
else if (l > mid) return query(rson, l, r);
else return query(lson, l, mid) & query(rson, mid + , r);
} void Work(int i, int L, int R){
tree[i] |= tree[i >> ];
if (L == R){ ans[++ret] = tree[i]; return ;}
int mid = (L + R) >> ;
Work(lson);
Work(rson);
} int main(){ scanf("%d%d", &n, &m); memset(tree, , sizeof tree);
rep(i, , m){
scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].val);
update(, , n, a[i].l, a[i].r, a[i].val);
} bool flag = true; rep(i, , m){
int cnt = query(, , n, a[i].l, a[i].r);
if (cnt != a[i].val){
flag = false;
break;
}
} if (flag) Work(, , n); else return * puts("NO");
puts("YES"); rep(i, , ret) printf("%d ", ans[i]); return ;
}
上一篇:Linux 查看系统硬件信息汇总 (部份实例详解Centoso为例)


下一篇:Codeforces 482B Interesting Array