0w1

CFR 483 D. Interesting Array ( OR / AND Segment Tree )

Problem - D - Codeforces
Let's try to simulate. First we have lazy-propagation on discretized segment tree where it only creates nodes when really needed, that is, the total memory consumption will be about O( M lg N ). The objective is clear, for each query ( L, R, Q ), we want the and value of [ L, R ] be Q. We intuitively know that if we greedily perform OR upon range [ L, R ] with value Q, it is the best, because it is the minimum requirement for that particular query, and affects the least to other queries ( if have ORed some superfluous values, might cause other queries AND up with a larger value than what they need ). Therefore we will OR upon each query, and at last verify whether the conditions all meet. Note that when making the AND queries, the default value should be all ones in bits form.

const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXQ = 1 << 30;

int N, M;
int L[ MAXM ], R[ MAXM ], Q[ MAXM ];

struct itvt{
    int and_val;
    int or_tag;
    itvt *lc, *rc;
    itvt() : lc( NULL ), rc( NULL ){
        or_tag = 0;
        and_val = 0;
    }
    void push(){
        if( or_tag ){
            lc->or_tag |= or_tag;
            lc->and_val |= or_tag;
            rc->or_tag |= or_tag;
            rc->and_val |= or_tag;
            or_tag = 0;
        }
    }
    void pull(){
        and_val = lc->and_val & rc->and_val;
    }
    void update( int lb, int rb, int ql, int qr, int v ){
        if( qr <= lb or rb <= ql ) return;
        if( ql <= lb and rb <= qr ){
            and_val |= v;
            or_tag |= v;
            return;
        }
        push();
        int mid = lb + rb >> 1;
        lc->update( lb, mid, ql, qr, v );
        rc->update( mid, rb, ql, qr, v );
        pull();
    }
    int query( int lb, int rb, int ql, int qr ){
        if( qr <= lb or rb <= ql ) return ~( 1 << 31 ); // !!!!
        if( ql <= lb and rb <= qr ) return and_val;
        push();
        int mid = lb + rb >> 1;
        int res = lc->query( lb, mid, ql, qr ) & rc->query( mid, rb, ql, qr );
        pull();
        return res;
    }
};

itvt* build_itvt( int lb, int rb ){
    itvt *t = new itvt();
    if( lb + 1 == rb ) return t;
    int mid = lb + rb >> 1;
    t->lc = build_itvt( lb, mid );
    t->rc = build_itvt( mid, rb );
    return t;
}

void solve(){
    int N, M; cin >> N >> M;
    for( int i = 0; i < M; ++i )
        cin >> L[ i ] >> R[ i ] >> Q[ i ];

    itvt *root = build_itvt( 0, N );
    for( int i = 0; i < M; ++i )
        root->update( 0, N, L[ i ] - 1, R[ i ], Q[ i ] );

    for( int i = 0; i < M; ++i )
        if( root->query( 0, N, L[ i ] - 1, R[ i ] ) != Q[ i ] ){
            cout << "NO\n";
            return;
        }

    cout << "YES\n";
    for( int i = 0; i < N; ++i )
        cout << root->query( 0, N, i, i + 1 ) << " \n"[ i + 1 == N ];
}