原题链接
题意：
要求构造一个序列，使得满足m个条件，a[l[i]]&a[l[i]+1]&……&a[r[i]]==q[i]
思路：
根据&的性质，两个数&时，拆成二进制后，当两位都为1时，才是1。所以我们可以对[l,r]的数都|q，这样每一位都是q，这次操作里一定满足条件。对所有的条件都做这种操作，最后检验每个区间的数求&和是否还等于q即可，如果可以构造出来的话，查询值输出。可以用线段树维护区间修改|，区间和单点求&和的过程。
代码：
const int maxn=1e5+100; struct node { int l,r,val,laz; } tr[maxn*4]; struct node1 { int l,r,q; } qus[maxn]; int n,m; void pushup(int u){ tr[u].val=tr[u<<1].val&tr[u<<1|1].val; } void pushdown(int u){ if(tr[u].laz){ tr[u<<1].laz|=tr[u].laz; tr[u<<1|1].laz|=tr[u].laz; tr[u<<1].val|=tr[u].laz; tr[u<<1|1].val|=tr[u].laz; tr[u].laz=0; } } void build(int u,int l,int r){ tr[u]={l,r,0,0}; if(l==r) return ; int mid=(l+r)/2; build(u<<1,l,mid);build(u<<1|1,mid+1,r); } void update(int l,int r,int val,int u){ if(l<=tr[u].l&&r>=tr[u].r){ tr[u].laz|=val;tr[u].val|=val; return ; } pushdown(u); int mid=(tr[u].l+tr[u].r)/2; if(l<=mid) update(l,r,val,u<<1); if(mid<r) update(l,r,val,u<<1|1); pushup(u); } int qask(int u,int l,int r){ if(l<=tr[u].l&&r>=tr[u].r){ return tr[u].val; } pushdown(u); int mid=(tr[u].l+tr[u].r)/2; int res=(1<<31)-1;///开始让每一位都是1 if(l<=mid) res=res&qask(u<<1,l,r); if(mid<r) res=res&qask(u<<1|1,l,r); return res; } int main() { n=read(),m=read(); build(1,1,n); for(int i=1;i<=m;i++){ qus[i].l=read(),qus[i].r=read(),qus[i].q=read(); update(qus[i].l,qus[i].r,qus[i].q,1); } bool flag=1; for(int i=1;i<=m;i++) if(qask(1,qus[i].l,qus[i].r)!=qus[i].q){ puts("NO");flag=0;return 0; } puts("YES"); for(int i=1;i<=n;i++) printf("%d ",qask(1,i,i)); return 0; }
