2017-10-22模拟赛T2 或(or.*)

题面

【题目描述】
你需要构造一个长度为 n 的数列 X，当中的数字范围从 0 到 2^30-1。除此之外你需要
满足 m 个条件，第 i 个条件为 X[li]|X[li+1]|……|X[ri]=pi。|为按位或运算。
【输入描述】
第一行输入两个整数 n,m
接下来的 m 行每行输入三个整数 li,ri,pi
【输出描述】
如果存在这样的序列，第一行输出 Yes，否则输出 No。
如果存在这样的序列，第二行输出 n 个数，为数列 X。
【样例】
输入
2 1
1 2 1

输出
Yes
1 1
【数据范围】
对于 30%的数据，n,m<=1000。
对于另外 30%的数据，pi<=1。
对于 100%的数据，n,m<=100000，1<=li<=ri<=n，0<=pi<2^30。

题解

又是一道位运算的题目（感觉是最简单的一道……）

题意还是比较清楚的，这里不细说了。

"对于另外30%的数据"，出题人在这里是不是给了一个小小的提示？

众所周知，位运算有一个性质，即对于每一个位是独立的，因此想到分开考虑每个位的情况。

对于每个条件的pi的每一位，如果这一位为0，那么这个区间内所有的数的这一位显然都为0。

因此想到如下做法：

先把数列内所有数设为2³⁰-1。

对于每个条件的pi的每一位，如果这一位为0，那么将该区间内所有数的这一位置0，最后判断每个条件是否成立即可。

用线段树维护数列，只需记录区间内所有数的或即可。复杂度O(mlog₂n)

具体细节见代码。关于位运算的操作，这里不多说了。

代码

 #include <stdio.h>

 #define N 100010

 #define reg register

 const int pv=(<<)-;

 int n,m,l[N],r[N],a[N];

 struct node{int o,l;}t[];

 void build(int l,int r,int k) {

     t[k].o=pv;t[k].l=;

     if(l!=r) {

         build(l,l+r>>,k<<);

         build((l+r>>)+,r,k<<|);

     }

 }

 void pushdown(int k) {

     reg int x=t[k].l;

     t[k<<].o&=~x;

     t[k<<].l|=x;

     t[k<<|].o&=~x;

     t[k<<|].l|=x;

     t[k].l=;

 }

 void setzero(int l,int r,int a,int b,int c,int k) {

     if(l==a&&r==b) {

         t[k].o&=~c;t[k].l|=c;

         return;

     }

     pushdown(k);

     reg int mid=l+r>>;

     if(b<=mid) setzero(l,mid,a,b,c,k<<);

     else if(a>mid) setzero(mid+,r,a,b,c,k<<|);

     else {

         setzero(l,mid,a,mid,c,k<<);

         setzero(mid+,r,mid+,b,c,k<<|);

     }

 }

 int query(int l,int r,int a,int b,int k) {

     if(l==a&&r==b) return t[k].o;

     pushdown(k);

     reg int mid=l+r>>;

     if(b<=mid) return query(l,mid,a,b,k<<);

     else if(a>mid) return query(mid+,r,a,b,k<<|);

     else {

         return query(l,mid,a,mid,k<<)|query(mid+,r,mid+,b,k<<|);

     }

 }

 void output(int l,int r,int k) {

     if(l==r) {

         printf("%d ",t[k].o);

         return;

     }

     pushdown(k);

     output(l,l+r>>,k<<);

     output((l+r>>)+,r,k<<|);

 }

 int main() {

     scanf("%d%d",&n,&m);

     build(,n,);

     for(int i=;i<m;++i) {

         scanf("%d%d%d",l+i,r+i,a+i);

         setzero(,n,l[i],r[i],~a[i],);

     }

     for(int i=;i<m;++i) {

         if(query(,n,l[i],r[i],)!=a[i]) {

             puts("No");

             return ;

         }

     }

     puts("Yes");

     output(,n,);

     return ;

 }

巴特西

2017-10-22模拟赛T2 或(or.*)

最新文章

热门文章