Codeforces Round #275 (Div. 2)D. Interesting Array（线段树区间更新区间查询）

 1 #define bug(x) cout<<#x<<" is "<<x<<endl;
 2 #define IO std::ios::sync_with_stdio(0);
 3 #include <bits/stdc++.h>
 4 #define iter ::iterator
 5 using namespace  std;
 6 typedef long long ll;
 7 typedef pair<ll,ll>P;
 8 typedef pair<P,P>P1;
 9 #define mk make_pair
10 #define pb push_back
11 #define se second
12 #define fi first
13 #define rs o<<1|1
14 #define ls o<<1
15 const int N=1e5+5;
16 ll mod=1e9+7;
17 int n,m;
18 struct node{
19     int x,y,z;
20 }a[N];
21 int sumv[N*4],addv[N*4];
22 void push(int o){
23     sumv[o]=sumv[ls]&sumv[rs];
24 }
25 void down(int o){
26     if(addv[o]){
27         sumv[ls]|=addv[o];
28         sumv[rs]|=addv[o];
29         addv[ls]|=addv[o];
30         addv[rs]|=addv[o];
31         addv[o]=0;
32     }
33 }
34 void up(int o,int l,int r,int ql,int qr,int v){
35     if(l>=ql&&r<=qr){
36         sumv[o]|=v;
37         addv[o]|=v;
38         return;
39     }
40     int m=(l+r)/2;
41     down(o);
42     if(ql<=m)up(ls,l,m,ql,qr,v);
43     if(qr>m)up(rs,m+1,r,ql,qr,v);
44     push(o);
45 }
46 int qu(int o,int l,int r,int ql,int qr){
47     if(l>=ql&&r<=qr){
48         return sumv[o];
49     }
50     int m=(l+r)/2;
51     int res=(1<<30)-1;
52     down(o);
53     if(ql<=m)res=res&qu(ls,l,m,ql,qr);
54     if(qr>m)res=res&qu(rs,m+1,r,ql,qr);
55     push(o);
56     return res;
57 }
58 void work(int o,int l,int r){
59     if(l==r){
60         if(l!=n)cout<<sumv[o]<<" ";
61         else cout<<sumv[o]<<endl;
62         return;
63     }
64     int m=(l+r)/2;
65     down(o);
66     work(ls,l,m);
67     work(rs,m+1,r);
68 }
69 int main(){
70     IO;
71     cin>>n>>m;
72     for(int i=1;i<=m;i++){
73         cin>>a[i].x>>a[i].y>>a[i].z;
74         up(1,1,n,a[i].x,a[i].y,a[i].z);
75     }
76     int flag=0;
77     for(int i=1;i<=m;i++){
78         int res=qu(1,1,n,a[i].x,a[i].y);
79         if(res!=a[i].z){
80             flag=1;
81             break;
82         }
83     }
84     if(!flag){
85         cout<<"YES"<<endl;
86         work(1,1,n);
87     }
88     else cout<<"NO"<<endl;
89 }