codeforces - Interesting Array

题目链接：Interesting Array

题目大意：题目要我们构造一个序列，满足m个条件，m个区间的与值为x，问我们是否能够构造出来，若不能输出NO，若可以则输出YES并输出，构造出的序列。

一道线段树好题。这道题我们要用到与运算的性质。要让我们当前区间的区间与为x，那么我们可以想到，我们区间的每个数字的每一位（二进制每一位），若x在这一位有1，那么区间所有数字都必须为1.因为只要有一个不是1，那么这一位就不会有1了，然后就不会等于x。怎么让每个数字的每一位与x相等呢？我们让区间每个数字或运算上x即可。所以我们最后计算每个需要满足的区间是否为需要满足的值即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,l[N],r[N],x[N],flag;
struct node{
	int l,r,sum,lazy;
}t[N<<2];
inline void push_up(int p){
	t[p].sum=t[p<<1].sum&t[p<<1|1].sum;
}
inline void push_down(int p){
	if(t[p].lazy){
		t[p<<1].sum|=t[p].lazy;	t[p<<1|1].sum|=t[p].lazy;
		t[p<<1].lazy|=t[p].lazy; t[p<<1|1].lazy|=t[p].lazy;
		t[p].lazy=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l;	t[p].r=r;
	if(l==r)	return ;	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r,int x){
	if(t[p].l==l&&t[p].r==r){
		t[p].sum|=x;	t[p].lazy|=x;	return ;
	}
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	change(p<<1,l,r,x);
	else if(l>mid)	change(p<<1|1,l,r,x);
	else	change(p<<1,l,mid,x),change(p<<1|1,mid+1,r,x);
	push_up(p);
}
int ask(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].sum;
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return ask(p<<1,l,mid)&ask(p<<1|1,mid+1,r);
}
int out(int p,int x){
	if(t[p].l==t[p].r)	return t[p].sum;
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	return out(p<<1,x);
	else	return out(p<<1|1,x);
}
signed main(){
	scanf("%d %d",&n,&m);	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&l[i],&r[i],&x[i]);
		change(1,l[i],r[i],x[i]);
	}
	for(int i=1;i<=m&&!flag;i++){
		if(ask(1,l[i],r[i])!=x[i])	flag++;
	}
	if(flag)	return puts("NO"),0;	puts("YES");
	for(int i=1;i<=n;i++)	printf("%d ",out(1,i));puts("");
	return 0;
}