CodeForces 482B. Interesting Array（线段树）

末蓝、 2021-10-13 16:30 206阅读 0赞

## 题意：构造出一个序列，满足下面m个要求：每一个要求的组成是l,r,q三个数，表示从a\[l\]&a\[l+1\]....&a\[r\]的值为q，问能不能构造出这样的序列。 ##

## 分析：刚开始还想着建对每一位建立线段树，后面发现直接用异或运算维护一颗线段树就好了。s\[i\]表示该区间的&的值，先满足所有要求，s\[i\]|q来满足。最后判断每个s\[i\]的值是否还为原值，若不是，则无法构造。否则叶子节点就是构造的序列。 ##

## 代码： ##

#include <iostream>
    using namespace std;
    #define ll long long
    const int N = 1e6+5;
    int s[N<<2],lz[N<<2],l[N],r[N],q[N],n,m,I;
    
    void pushup(int k) {
        s[k] = s[k<<1]&s[k<<1|1];
    }
    
    void pushdown(int k,int ln,int rn) {
        if(lz[k]) {
            s[k<<1] |= lz[k];
            s[k<<1|1] |= lz[k];
            lz[k<<1] |= lz[k];
            lz[k<<1|1] |= lz[k];
            lz[k] = 0;
        }
    }
    
    void build(int k,int l,int r) {
        lz[k] = 0;
        if(l==r) {
            s[k]=0;
            return;
        }
        int mid = (l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        pushup(k);
    }
    
    void update(int k,int L,int R,int l,int r,int val)
    {
        if(L<=l&&r<=R) {
            s[k] |= val;
            lz[k] |= val;
            return;
        }
        int mid = (l+r)/2;
        int ln = mid-l+1;
        int rn = r-mid;
        pushdown(k,ln,rn);
        if(L<=mid) update(k<<1,L,R,l,mid,val);
        if(mid<R) update(k<<1|1,L,R,mid+1,r,val);
        pushup(k);
    }
    
    int qu(int k,int L,int R,int l,int r) {
        if(L<=l&&r<=R) return s[k];
        int mid = (l+r)>>1;
        int ln = mid-l+1;
        int rn = r-mid;
        pushdown(k,ln,rn);
        ll I = (ll)(2<<30) - 1;
        if(L<=mid) I = I&qu(k<<1,L,R,l,mid);
        if(mid<R) I = I&qu(k<<1|1,L,R,mid+1,r);
        pushup(k);
        return I;
    }
    
    int main() {
        cin >> n >> m;
        build(1,1,n);
        for(int i = 0;i<m;i++) {
            cin >> l[i] >> r[i] >> q[i];
            update(1,l[i],r[i],1,n,q[i]);
        }
        for(int i = 0;i<m;i++) {
            int ans = qu(1,l[i],r[i],1,n);
            if(ans!=q[i]) {
                cout << "NO" << endl;
                return 0;
            }
        }
        cout << "YES" << endl;
        for(int i = 1;i<=n;i++)
            cout << qu(1,i,i,1,n) << " ";
        return 0;
    }