【题目】点击打开链接
【题意】
给出若干个条件,让一个序列满足从第Li个数到第Ri个数的&和为Qi;问是否存在这个序列,若存在,输出YES,并输出这个序列,否则输出NO.
思路:线段树区间覆盖,对于每一个条件,对这个区间上的每一个数都|上询问的数。操作完之后,在检查每个询问是否成立。
【AC 代码】
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
struct Q{
int l,r,o;
}q[maxn];
struct node{
int l,r,lazy;
int AND;
}Tree[maxn<<2];
void pushdown(int rt){
if(Tree[rt].lazy){
Tree[rt*2].lazy|=Tree[rt].lazy;
Tree[rt*2+1].lazy|=Tree[rt].lazy;
Tree[rt*2].AND|=Tree[rt].lazy;
Tree[rt*2+1].AND|=Tree[rt].lazy;
Tree[rt].lazy=0;
}
}
void Build(int l,int r,int rt)
{
Tree[rt].l=l,Tree[rt].r=r;
Tree[rt].lazy=Tree[rt].AND=0;
if(l==r) return ;
int mid=(l+r)/2;
Build(l,mid,rt*2);
Build(mid+1,r,rt*2+1);
}
void update(int L,int R,int c,int rt)
{
if(L==Tree[rt].l&&Tree[rt].r==R){
Tree[rt].lazy|=c;
Tree[rt].AND|=c;
return ;
}
pushdown(rt);
int mid=(Tree[rt].l+Tree[rt].r)/2;
if(R<=mid) update(L,R,c,rt*2);
else if(L>mid) update(L,R,c,rt*2+1);
else{
update(L,mid,c,rt*2);
update(mid+1,R,c,rt*2+1);
}
}
int queryans(int L,int R,int rt)
{
if(L==Tree[rt].l&&Tree[rt].r==R){
return Tree[rt].AND;
}
pushdown(rt);
int mid=(Tree[rt].l+Tree[rt].r)/2;
if(R<=mid) return queryans(L,R,rt*2);
else if(L>mid) return queryans(L,R,rt*2+1);
else{
return queryans(L,mid,rt*2)&queryans(mid+1,R,rt*2+1);
}
}
void output(int rt)
{
if(Tree[rt].l==Tree[rt].r){
printf("%d ",Tree[rt].AND);
return ;
}
pushdown(rt);
output(rt*2);
output(rt*2+1);
}
int main()
{
int n,m;
cin>>n>>m;
Build(1,n,1);
for(int i=1; i<=m; i++){
cin>>q[i].l>>q[i].r>>q[i].o;
update(q[i].l,q[i].r,q[i].o,1);
}
for(int i=1; i<=m; i++){
int ans=queryans(q[i].l,q[i].r,1);
if(ans!=q[i].o){
puts("NO");
return 0;
}
}
puts("YES");
output(1);
}