CodeForces 482B Interesting Array 线段树 - c++编程基础

B. Interesting Array time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

We'll call an array of n non-negative integers a[1],?a[2],?...,?a[n] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1?≤?li?≤?ri?≤?n) meaning that value $\$ should be equal to qi.

Your task is to find any interesting array of n elements or state that such array doesn't exist.

Expression x&y means the bitwise AND of numbers x and y. In programming languages C++, Java and Python this operation is represented as &, in Pascal — as and.

Input

The first line contains two integers n, m (1?≤?n?≤?105, 1?≤?m?≤?105) — the number of elements in the array and the number of limits.

Each of the next m lines contains three integers li, ri, qi (1?≤?li?≤?ri?≤?n, 0?≤?qi?i-th limit.

Output

If the interesting array exists, in the first line print YES (without the quotes) and in the second line print n integers a[1],?a[2],?...,?a[n](0?≤?a[i]?

If the interesting array doesn't exist, print NO (without the quotes) in the single line.

Sample test(s) input

3 1
1 3 3

output

YES
3 3 3

input

3 2
1 3 3
1 3 2

output

NO

题意：给m个区间及区间内每个数&值,问存不存在这样一个数列满足。

分析：对于每一个区间[l,r]&值为q，那么说明这个区间每一个数都得或q。用线段树维护下区间更新,，注意向下更新是或，向上合并是与。最后查询下各自的区间看值是否满足。满足再输出对应的单个点的值。

/**
 * @author neko01
 */
//#pragma comment(linker, /STACK:102400000,102400000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include
            using namespace std; typedef long long LL; #define min3(a,b,c) min(a,min(b,c)) #define max3(a,b,c) max(a,max(b,c)) #define pb push_back #define mp(a,b) make_pair(a,b) #define clr(a) memset(a,0,sizeof a) #define clr1(a) memset(a,-1,sizeof a) #define dbg(a) printf(%d ,a) typedef pair
            
              pp; const double eps=1e-8; const double pi=acos(-1.0); const int INF=0x7fffffff; const LL inf=(((LL)1)<<61)+5; const int N=100005; struct node{ int l,r; int col; int val; }tree[N*4]; void build(int x,int l,int r) { tree[x].l=l,tree[x].r=r; tree[x].col=tree[x].val=0; if(l==r) return; int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); } inline void push_down(int x) { if(tree[x].col!=0) { tree[x<<1].col|=tree[x].col; tree[x<<1|1].col|=tree[x].col; tree[x<<1].val|=tree[x].col; tree[x<<1|1].val|=tree[x].col; tree[x].col=0; } } void update(int x,int l,int r,int val) { if(tree[x].l==l&&tree[x].r==r) { tree[x].val|=val; tree[x].col|=val; return; } push_down(x); int mid=(tree[x].l+tree[x].r)>>1; if(r<=mid) update(x<<1,l,r,val); else if(l>mid) update(x<<1|1,l,r,val); else { update(x<<1,l,mid,val); update(x<<1|1,mid+1,r,val); } tree[x].val=tree[x<<1].val&tree[x<<1|1].val; } int query(int x,int l,int r) { if(tree[x].l==l&&tree[x].r==r) return tree[x].val; push_down(x); int mid=(tree[x].l+tree[x].r)>>1; if(r<=mid) return query(x<<1,l,r); else if(l>mid) return query(x<<1|1,l,r); else return query(x<<1,l,mid)&query(x<<1|1,mid+1,r); } int l[N],r[N],q[N]; int main() { int n,m; scanf(%d%d,&n,&m); build(1,1,n); for(int i=0;i
             
              ?