题解 CF482B 【Interesting Array】

线段树

乍一看是一个构造题，其实我们发现，如果这段区间这一位的值为1，那么整段区间都要为1，直接区间赋值1就行了，把每一位合起来就是区间or a[i]

但是这样就有可能出现0的位置也为1的情况，所以我们对所有的区间都再查询一遍，看看我们构造出来的是不是有0的位置变成1，如果有冲突就输出NO

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N=100005;
struct node {
  int l,r,k;
}q[N<<2];
int a[N<<2],tag[N<<2],n,m;
bool vis=1;
void pushup(int x) {a[x]=a[x<<1]&a[x<<1|1];}
void pushdown(int x) {
  a[x<<1]|=tag[x];
  a[x<<1|1]|=tag[x];
  tag[x<<1]|=tag[x];
  tag[x<<1|1]|=tag[x];
}
void modify(int x,int l,int r,int L,int R,int y) {
  if(L<=l && r<=R) {
    a[x]|=y,tag[x]|=y;
    return ;
  }
  pushdown(x);
  int mid=(l+r)>>1;
  if(L<=mid) modify(x<<1,l,mid,L,R,y);
  if(R>mid) modify(x<<1|1,mid+1,r,L,R,y);
  pushup(x);
}
int query(int x,int l,int r,int L,int R) {
  if(L<=l && r<=R) return a[x];
  pushdown(x);
  int ret=(1<<30)-1,mid=(l+r)>>1;
  if(L<=mid) ret=ret&query(x<<1,l,mid,L,R);
  if(R>mid) ret=ret&query(x<<1|1,mid+1,r,L,R);
  return ret;
}
int main() {
  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;++i) {
    scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
    if(q[i].l>q[i].r) swap(q[i].l,q[i].r);
    modify(1,1,n,q[i].l,q[i].r,q[i].k);
  }
  for (int i=1;i<=m;++i) {
    if(query(1,1,n,q[i].l,q[i].r)!=q[i].k) vis=0;
  }
  if(!vis) {
    puts("NO");
    return 0;
  }
  puts("YES");
  for (int i=1;i<n;++i) printf("%d ",query(1,1,n,i,i));
  printf("%d\n",query(1,1,n,n,n));
  return 0;
}