题目大意:构造一个序列$S$,有$m$条限制,每条为$l\;r\;q$,表示$\&_{i=l}^r S_i=q$
题解:每条限制就把$[l,r]$内的数或上$q$,最后判断就行了
卡点:我又写了一课$O(n^2\log_2n)$的线段树。。。
C++ Code:
#include <cstdio>
#include <cstdlib>
#define maxn 100010
const int inf = (1 << 30) - 1;
namespace SgT {
int n;
int L, R, q;
int V[maxn << 2], tg[maxn << 2];
inline void pushdown(int rt) {
int &x = tg[rt];
V[rt << 1] |= x;
V[rt << 1 | 1] |= x;
tg[rt << 1] |= x;
tg[rt << 1 | 1] |= x;
x = 0;
}
void modify(int rt, int l, int r) {
if (L <= l && R >= r) {
V[rt] |= q;
tg[rt] |= q;
return ;
}
if (tg[rt]) pushdown(rt);
int mid = l + r >> 1;
if (L <= mid) modify(rt << 1, l, mid);
if (R > mid) modify(rt << 1 | 1, mid + 1, r);
V[rt] = V[rt << 1] & V[rt << 1 | 1];
}
inline void add(int ll, int rr, int qq) {
L = ll, R = rr, q = qq;
modify(1, 1, n);
}
int query(int rt, int l, int r) {
if (L <= l && R >= r) return V[rt];
if (tg[rt]) pushdown(rt);
int mid = l + r >> 1, ans = inf;
if (L <= mid) ans = query(rt << 1, l, mid);
if (R > mid) ans &= query(rt << 1 | 1, mid + 1, r);
return ans;
}
inline int ask(int ll, int rr) {
L = ll, R = rr;
return query(1, 1, n);
}
}
using SgT::add;
using SgT::ask;
int n, m;
int l[maxn], r[maxn], q[maxn];
int main() {
scanf("%d%d", &n, &m); SgT::n = n;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", l + i, r + i, q + i);
add(l[i], r[i], q[i]);
}
for (int i = 1; i <= m; i++) {
if (ask(l[i], r[i]) != q[i]) {
puts("NO");
exit(0);
}
}
puts("YES");
for (int i = 1; i < n; i++) printf("%d ", ask(i, i));
printf("%d\n", ask(n, n));
return 0;
}