solution-cf482b

CaiXY06 · 2021-07-02 11:45:44 · 题解

看到神犇们都用各种数据结构过了这题，那我就来一篇 差分 的题解吧

题目要求构造一个序列，并且需要满足 m 个限制，每个限制都是要 [l,r] 的 按位与和 为 q。

那么我们可以对于每一位做一个 差分。

设当前考虑二进制下的第 i 位 (0\leq i\leq 30)。

如果这一位的差分值 >0 就说明这个数的二进制第 i 为 1，a_i=a_i+2^i。

我们在差分完之后，就满足了需要这一位为 1 的限制，但是并不满足不为 1 的限制，所以我们可以再做一个 前缀和 判断 [l,r] 这一段区间的差分值是否都 >1 ，如果是就输出无解的情况。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010],l[100010],r[100010],q[100010],c[100010],s[100010];
bool tag;
inline bool check(int x){
    memset(c,0,sizeof(c));
    for(int i=1;i<=m;i++)
    if(q[i]&x)c[l[i]]++,c[r[i]+1]--;//差分
    for(int i=1;i<=n;i++){
        c[i]+=c[i-1],s[i]=s[i-1]+(!c[i]);//前缀和
        if(c[i])a[i]|=x;
    }
    for(int i=1;i<=m;i++)
    if(!(q[i]&x)&&!(s[r[i]]-s[l[i]-1]))return 1;//判断是否无解
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&l[i],&r[i],&q[i]);
    for(int i=0;i<=30&&!tag;i++)tag=check(1<<i);//枚举每一位
    if(tag)return puts("NO"),0;
    puts("YES");
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
}