首页 > 代码库 > Codeforces 482B Interesting Array(线段树)
Codeforces 482B Interesting Array(线段树)
题目链接 Interesting Array
区间更新。然后对于每一个约数重新求一遍区间的&值,不符合就跳出。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define rep(i, a, b) for (int i(a); i <= (b); ++i) 6 #define lson i << 1, L, mid 7 #define rson i << 1 | 1, mid + 1, R 8 9 const int N = 100010; 10 11 struct node{ 12 int l, r, val; 13 } a[N]; 14 15 int tree[N << 2], ans[N]; 16 int n, m; 17 int ret = 0; 18 19 void update(int i, int L, int R, int l, int r, int val){ 20 if (L == l && R == r){ tree[i] |= val; return ;} 21 int mid = (L + R) >> 1; 22 if (r <= mid) update(lson, l, r, val); 23 else if (l > mid) update(rson, l, r, val); 24 else{ 25 update(lson, l, mid, val); 26 update(rson, mid + 1, r, val); 27 } 28 } 29 30 int query(int i, int L, int R, int l, int r){ 31 if (L == l && R == r) return tree[i]; 32 int mid = (L + R) >> 1; 33 if (r <= mid) return query(lson, l, r); 34 else if (l > mid) return query(rson, l, r); 35 else return query(lson, l, mid) & query(rson, mid + 1, r); 36 } 37 38 void Work(int i, int L, int R){ 39 tree[i] |= tree[i >> 1]; 40 if (L == R){ ans[++ret] = tree[i]; return ;} 41 int mid = (L + R) >> 1; 42 Work(lson); 43 Work(rson); 44 } 45 46 47 int main(){ 48 49 scanf("%d%d", &n, &m); 50 51 52 memset(tree, 0, sizeof tree); 53 rep(i, 1, m){ 54 scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].val); 55 update(1, 1, n, a[i].l, a[i].r, a[i].val); 56 } 57 58 bool flag = true; 59 60 rep(i, 1, m){ 61 int cnt = query(1, 1, n, a[i].l, a[i].r); 62 if (cnt != a[i].val){ 63 flag = false; 64 break; 65 } 66 } 67 68 if (flag) Work(1, 1, n); else return 0 * puts("NO"); 69 puts("YES"); rep(i, 1, ret) printf("%d ", ans[i]); 70 71 72 return 0; 73 }
Codeforces 482B Interesting Array(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。