YbtOJ NOIP2020 模拟赛 B 组 Day3 A.或位运算【差分】【前缀和】

题目：

传送门

题意：

对于一个长度为$n$的$x$序列，有$m$个形如$x_{l}or{x}_{l+1}\dots or{x}_{r?1}or{x}_r=p$需要满足
问是否能构造出这样的序列

分析：

对于$or$操作，我们是无法通过$p$的$1$的位置来限定$x$的$1$的位置，但根据$or$的定义，我们可以知道，对于$0$的位置$x$对应的位置也只能是$0$
我们可以通过差分数组来限定每个区间的$x$第$k$位是$0$，最后检测答案时弄一个前缀和，如果对于一个区间$l?r$的$x$在第$k$位都是$0$，但$p$在第$k$位是$1$，那这样肯定是不合法的

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#define LL long long
using namespace std;
inline LL read()
{
    LL s=0,f=1; char c=getchar();while(c<'0'||c>'9') {
    if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {
    s=s*10+c-'0';c=getchar();}return s*f;
}
int l[100005],r[100005],p[100005],sum[100005],ans[100005],s[100005];
int main()
{
    freopen("or.in","r",stdin);freopen("or.out","w",stdout);int n=read(),m=read();for(int i=1;i<=m;i++) l[i]=read(),r[i]=read(),p[i]=read();for(int i=0;i<30;i++){
    memset(sum,0,sizeof(sum));memset(s,0,sizeof(s));for(int j=1;j<=m;j++) if(!(p[j]&(1<<i))) sum[l[j]]++,sum[r[j]+1]--;for(int j=1;j<=n;j++) sum[j]+=sum[j-1];for(int j=1;j<=n;j++){
    s[j]=s[j-1]+(sum[j]?1:0);if(!sum[j]) ans[j]|=(1<<i);}for(int j=1;j<=m;j++) if((p[j]&(1<<i))&&r[j]-l[j]+1==s[r[j]]-s[l[j]-1]) return !printf("No");}printf("Yes\n");for(int i=1;i<=n;i++) printf("%d ",ans[i]);return 0;
}