CF482 B. Interesting Array

题目传送门：https://codeforces.com/problemset/problem/482/B

题目大意：
给定\(m\)条限制，每条限制形如\(l_i,r_i,p_i\)，表示序列\(A\)的\(A_{l_i}\&A_{l_i+1}\&...\&A_{r_i}=p_i\)，问是否存在序列\(A\)满足\(m\)条限制

因为需要满足\(A_{l_i}\&A_{l_i+1}\&...\&A_{r_i}=p_i\)，故\(A_{l_i}\sim A_{r_i}\)中的每一个数都至少含有\(p_i\)，即\(A_j(l_i\leqslant j\leqslant r_i)\)必然可以表示为\(A_j=p_i|\alpha\)（ \(|\) 表示或）

故我们可以每次给区间\([l_i,r_i]\)的所有数或上\(p_i\)，然后再依次判断限制是否满足，最后单点查询输出即可

/*program from Wolfycz*/
#include
#include
#include
#include
#include
#include
#include
#define Fi first
#define Se second
#define ll_inf 1e18
#define MK make_pair
#define sqr(x) ((x)*(x))
#define pii pair
#define int_inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
templateinline T frd(T x){
	int f=1; char ch=gc();
	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')    f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
templateinline T read(T x){
	int f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
inline void print(int x){
	if (x<0)	putchar('-'),x=-x;
	if (x>9)	print(x/10);
	putchar(x%10+'0');
}
const int N=1e5;
struct S1{
	#define ls (p<<1)
	#define rs (p<<1|1)
	int Tree[(N<<2)+10],Lazy[(N<<2)+10];
	void update(int p){Tree[p]=Tree[ls]&Tree[rs];}
	void Add_Tag(int p,int V){Tree[p]|=V,Lazy[p]|=V;}
	void pushdown(int p){
		if (!Lazy[p])	return;
		Add_Tag(ls,Lazy[p]);
		Add_Tag(rs,Lazy[p]);
		Lazy[p]=0;
	}
	void Modify(int p,int l,int r,int L,int R,int V){
		if (L<=l&&r<=R){
			Add_Tag(p,V);
			return;
		}
		pushdown(p);
		int mid=(l+r)>>1;
		if (L<=mid)	Modify(ls,l,mid,L,R,V);
		if (R>mid)	Modify(rs,mid+1,r,L,R,V);
		update(p);
	}
	int Query(int p,int l,int r,int L,int R){
		if (L<=l&&r<=R)	return Tree[p];
		pushdown(p);
		int mid=(l+r)>>1,res=-1;
		if (L<=mid)	res&=Query(ls,l,mid,L,R);
		if (R>mid)	res&=Query(rs,mid+1,r,L,R);
		return res;
	}
	#undef ls
	#undef rs
}ST;//Segment Tree
struct node{
	int l,r,v;
	node(){l=r=v=0;}
	void Read(){l=read(0),r=read(0),v=read(0);}
}Ask[N+10];
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n=read(0),m=read(0);
	for (int i=1;i<=m;i++)	Ask[i].Read();
	for (int i=1;i<=m;i++)	ST.Modify(1,1,n,Ask[i].l,Ask[i].r,Ask[i].v);
	for (int i=1;i<=m;i++){
		int res=ST.Query(1,1,n,Ask[i].l,Ask[i].r);
		if (res!=Ask[i].v){
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	for (int i=1;i<=n;i++)	printf("%d%c",ST.Query(1,1,n,i,i),i==n?'\n':' ');
	return 0;
}
数据结构线段树OJCodeforces

相关

标签