1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
| #include <bits/stdc++.h> #define MAXN 100005 using namespace std; int ans[MAXN]; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } namespace SegmentTree{ struct node{ int l,r; int val,tag; }tree[MAXN<<2]; #define lc i<<1 #define rc i<<1|1 inline void pushup(int i){ tree[i].val=tree[lc].val&tree[rc].val; } inline void pushdown(int i){ if (tree[i].tag){ tree[lc].tag|=tree[i].tag; tree[rc].tag|=tree[i].tag; tree[lc].val|=tree[i].tag; tree[rc].val|=tree[i].tag; tree[i].tag=0; } } void Build(int i,int l,int r){ tree[i].l=l,tree[i].r=r; tree[i].val=tree[i].tag=0; if (l==r) return ; int mid=(l+r)>>1; Build(lc,l,mid); Build(rc,mid+1,r); } void Update(int i,int L,int R,int val){ if (L<=tree[i].l&&tree[i].r<=R){ tree[i].val|=val; tree[i].tag|=val; return ; } pushdown(i); int mid=(tree[i].l+tree[i].r)>>1; if (L<=mid) Update(lc,L,R,val); if (mid<R) Update(rc,L,R,val); pushup(i); } int Query(int i,int L,int R){ if (L<=tree[i].l&&tree[i].r<=R){ return tree[i].val; } pushdown(i); int mid=(tree[i].l+tree[i].r)>>1; if (L>mid) return Query(rc,L,R); else if (mid>=R) return Query(lc,L,R); else return Query(lc,L,R)&Query(rc,L,R); } void Out(int i){ if (tree[i].l==tree[i].r){ ans[tree[i].l]=tree[i].val; return ; } pushdown(i); Out(lc); Out(rc); } } using namespace SegmentTree; int ql[MAXN],qr[MAXN],qp[MAXN]; int main(){ int n=read(),m=read(); Build(1,1,n); for (register int i=1;i<=m;++i){ ql[i]=read(),qr[i]=read(),qp[i]=read(); Update(1,ql[i],qr[i],qp[i]); } Out(1); for (register int i=1;i<=m;++i){ if (Query(1,ql[i],qr[i])!=qp[i]){ puts("NO"); return 0; } } puts("YES"); for (register int i=1;i<=n;++i){ printf("%d ",ans[i]); } }
|