CF482B - Interesting Array
大意
你需要构造一组解，满足给定的不同要求，每次的要求是 \(l, r, x\)，必须保证 \(a_l \& a_{l + 1} \dots \& a_{r - 1} \& a_r = x\)。
思路
考虑用线段树构造。
对于这个题目，我们首先想到的是按位与的区间与是 \(x\)，每次至少得把这个区间的每一个数都按位或上 \(x\)，由此可知我们的 update 就是按位或，为了保证我们最终的答案是否可行，只需要把原始要求记一下，最后判断这些玩意的按位与是否和原来相同。
不难想到这样构造是唯一的，于是完。
代码
#include<iostream>
using namespace std;#define lc u << 1
#define rc u << 1 | 1
const int MAXN = 1e5 + 5;int n, m;struct node{int l, r;int val, sum;int tag;
}t[MAXN * 4];void build(int u, int l, int r){t[u] = {l, r, 0, 0};if(l == r){
// t[u].sum = (1 << 30) - 1;return;}int mid = (l & r) + ((l ^ r) >> 1);build(lc, l, mid);build(rc, mid + 1, r);
}void pushdown(int u){if(t[u].tag){t[lc].sum |= t[u].tag;t[rc].sum |= t[u].tag;t[lc].tag |= t[u].tag;t[rc].tag |= t[u].tag;t[u].tag = 0;}
}void pushup(int u){t[u].sum = t[lc].sum & t[rc].sum;
}void update(int u, int l, int r, int k){if(l <= t[u].l && t[u].r <= r){t[u].tag |= k;t[u].sum |= k;return;}pushdown(u);int mid = (t[u].l & t[u].r) + ((t[u].l ^ t[u].r) >> 1);if(l <= mid) update(lc, l, r, k);if(r > mid) update(rc, l, r, k);pushup(u);
}int query(int u, int l, int r){if(l <= t[u].l && t[u].r <= r){return t[u].sum;}pushdown(u);int ans = (1 << 30) - 1;int mid = (t[u].l & t[u].r) + ((t[u].l ^ t[u].r) >> 1);if(l <= mid){ans &= query(lc, l, r);}if(r > mid){ans &= query(rc, l, r);}return ans;
}int l[MAXN], r[MAXN], x[MAXN];int main(){cin >> n >> m;build(1, 1, n);for(int i = 1;i <= m;i ++){cin >> l[i] >> r[i] >> x[i];update(1, l[i], r[i], x[i]);}for(int i = 1;i <= m;i ++){if(query(1, l[i], r[i]) != x[i]){cout << "NO\n";return 0;}}cout << "YES\n";for(int i = 1;i <= n;i ++){cout << query(1, i, i) << ' ';}return 0;
}