题目大意
构造一个序列 \(a\)，使其满足若干限制条件，每个限制条件是形如 l r q 的式子，其意义是：\(\&_{i=l}^ra_i=q\)。
题意分析
看上去是构造题，实际上是数据结构题。
我们不妨先令初始时 \(a\) 为一个全 \(0\) 序列，再逐一看每个限制条件。
为了满足某一个限制条件 \(l,r,p\)，\([l,r]\) 区间的数必须符合以下两点：
- \(1\)，在二进制表示中，\(p\) 为 \(1\) 的位置均为 \(1\)。
- \(2\)，在二进制表示中，\(p\) 为 \(0\) 的位置区间内至少有一个数该位为 \(0\)。
我们发现，同时构造出满足两个条件的序列比较麻烦，且不好判断无解，因此，我们可以让一个条件成为构造的依据，另一个条件成为判断的依据。
具体的说，我们只需要构造出满足其中一个条件的序列，再逐一判断每个区间是否满足另一个条件即可。
因此，我们不妨先构造一个满足条件 \(1\) 的序列，再逐一对条件 \(2\) 进行判断。
那么，现在问题就变成了如果构造一个满足条件 \(1\) 的序列和如何对条件 \(2\) 进行判断。
这其实很简单，我们只需要用线段树进行区间按位或和区间求按位与就行了。
这是因为为了满足条件 \(1\)，我们需要让区间的二进制表示包含 \(p\)，这等价于于区间按位或 \(p\)，而条件 \(2\) 与区间的按位与是 \(p\) 二者也等价。
综上，我们只需要维护一颗线段树，支持区间或和区间求与即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m,inp[N][3];
struct STn{int l,r,t,sum;};//sum表示区间与的结果，t是懒标记
struct ST{
STn a[N<<2];
void or_t(int p,int k){
a[p].t|=k;a[p].sum|=k;//都或上k
}
void push_down(int p){//下放懒标记
if(a[p].t){
or_t(p<<1,a[p].t);
or_t(p<<1|1,a[p].t);
a[p].t=0;
}
}
void build(int p,int l,int r){//简单建树
a[p].l=l;a[p].r=r;a[p].t=0;
if(a[p].l==a[p].r) return ;
int mid=(a[p].l+a[p].r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void or_all(int p,int l,int r,int k){//区间或
if(l<=a[p].l&&a[p].r<=r){or_t(p,k);return ;}
push_down(p);int mid=(a[p].l+a[p].r)>>1;
if(l<=mid) or_all(p<<1,l,r,k);
if(r>mid) or_all(p<<1|1,l,r,k);
a[p].sum=a[p<<1].sum&a[p<<1|1].sum;
}
int and_all(int p,int l,int r){//区间求与
if(l<=a[p].l&&a[p].r<=r) return a[p].sum;
push_down(p);int mid=(a[p].l+a[p].r)>>1;
if(r<=mid) return and_all(p<<1,l,r);
if(l>mid) return and_all(p<<1|1,l,r);
return and_all(p<<1,l,r)&and_all(p<<1|1,l,r);
}
void print(int p){//输出序列
if(a[p].l==a[p].r){cout<<a[p].sum<<' ';return ;}
push_down(p);int mid=(a[p].l+a[p].r)>>1;
print(p<<1);print(p<<1|1);
}
}tree;
int main(){
scanf("%d%d",&n,&m);
tree.build(1,1,n);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&inp[i][0],&inp[i][1],&inp[i][2]);
tree.or_all(1,inp[i][0],inp[i][1],inp[i][2]);
}
for(int i=1;i<=m;i++)
if(tree.and_all(1,inp[i][0],inp[i][1])!=inp[i][2]){cout<<"NO\n";return 0;}
cout<<"YES\n";
tree.print(1);
return 0;
}