题面
【题目描述】
你需要构造一个长度为 n 的数列 X，当中的数字范围从 0 到 2^30-1。除此之外你需要
满足 m 个条件，第 i 个条件为 X[li]|X[li+1]|……|X[ri]=pi。|为按位或运算。
【输入描述】
第一行输入两个整数 n,m
接下来的 m 行每行输入三个整数 li,ri,pi
【输出描述】
如果存在这样的序列，第一行输出 Yes，否则输出 No。
如果存在这样的序列，第二行输出 n 个数，为数列 X。
【样例】
输入
2 1
1 2 1
输出
Yes
1 1
【数据范围】
对于 30%的数据，n,m<=1000。
对于另外 30%的数据，pi<=1。
对于 100%的数据，n,m<=100000，1<=li<=ri<=n，0<=pi<2^30。
题解
又是一道位运算的题目（感觉是最简单的一道……）
题意还是比较清楚的，这里不细说了。
"对于另外30%的数据"，出题人在这里是不是给了一个小小的提示？
众所周知，位运算有一个性质，即对于每一个位是独立的，因此想到分开考虑每个位的情况。
对于每个条件的pi的每一位，如果这一位为0，那么这个区间内所有的数的这一位显然都为0。
因此想到如下做法：
先把数列内所有数设为230-1。
对于每个条件的pi的每一位，如果这一位为0，那么将该区间内所有数的这一位置0，最后判断每个条件是否成立即可。
用线段树维护数列，只需记录区间内所有数的或即可。复杂度O(mlog2n)
具体细节见代码。关于位运算的操作，这里不多说了。
代码
#include <stdio.h>
#define N 100010
#define reg register
const int pv=(<<)-;
int n,m,l[N],r[N],a[N];
struct node{int o,l;}t[];
void build(int l,int r,int k) {
t[k].o=pv;t[k].l=;
if(l!=r) {
build(l,l+r>>,k<<);
build((l+r>>)+,r,k<<|);
}
}
void pushdown(int k) {
reg int x=t[k].l;
t[k<<].o&=~x;
t[k<<].l|=x;
t[k<<|].o&=~x;
t[k<<|].l|=x;
t[k].l=;
}
void setzero(int l,int r,int a,int b,int c,int k) {
if(l==a&&r==b) {
t[k].o&=~c;t[k].l|=c;
return;
}
pushdown(k);
reg int mid=l+r>>;
if(b<=mid) setzero(l,mid,a,b,c,k<<);
else if(a>mid) setzero(mid+,r,a,b,c,k<<|);
else {
setzero(l,mid,a,mid,c,k<<);
setzero(mid+,r,mid+,b,c,k<<|);
}
}
int query(int l,int r,int a,int b,int k) {
if(l==a&&r==b) return t[k].o;
pushdown(k);
reg int mid=l+r>>;
if(b<=mid) return query(l,mid,a,b,k<<);
else if(a>mid) return query(mid+,r,a,b,k<<|);
else {
return query(l,mid,a,mid,k<<)|query(mid+,r,mid+,b,k<<|);
}
}
void output(int l,int r,int k) {
if(l==r) {
printf("%d ",t[k].o);
return;
}
pushdown(k);
output(l,l+r>>,k<<);
output((l+r>>)+,r,k<<|);
}
int main() {
scanf("%d%d",&n,&m);
build(,n,);
for(int i=;i<m;++i) {
scanf("%d%d%d",l+i,r+i,a+i);
setzero(,n,l[i],r[i],~a[i],);
}
for(int i=;i<m;++i) {
if(query(,n,l[i],r[i],)!=a[i]) {
puts("No");
return ;
}
}
puts("Yes");
output(,n,);
return ;
}