CF482B. Interesting Array（线段树）

CF482B. Interesting Array（线段树）

​​原题链接​​题意： 要求构造一个序列，使得满足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=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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。