0w1

CFR 558 E. A Simple Task ( Segment Tree )

Problem - E - Codeforces
Quite creative a problem. If it were no problem E, I would have really thought performing brute force counting sort will somehow pass. Anyways, we will try bundling the same alphabets together for the sake of improving time complexity somehow. We will notice that with segment tree built and maintained for each alphabet, it is possible to retrieve counts for each alphabet in range [ ql, qr ] in total time complexity O( 26 * lg N ). Then we will clean the counts on each segment tree, and assign either by ascending or descending order depending on the input, by lazy propagation.

struct itvt{
    int lb, rb;
    int sum;
    int add_tag;
    int zero_tag;
    itvt *lc, *rc;
    itvt( int _l = -1, int _r = -1 ){
        lb = _l, rb = _r;
        sum = add_tag = 0;
        zero_tag = 0;
        lc = rc = NULL;
    }
    void push(){
        if( lb + 1 == rb ){
            add_tag = zero_tag = 0;
            return;
        }
        if( zero_tag ){
            lc->add_tag = lc->sum = 0;
            lc->zero_tag = 1;
            rc->add_tag = rc->sum = 0;
            rc->zero_tag = 1;
            zero_tag = 0;
        }
        lc->add_tag += add_tag;
        lc->sum += add_tag * ( lc->rb - lc->lb );
        rc->add_tag += add_tag;
        rc->sum += add_tag * ( rc->rb - rc->lb );
        add_tag = 0;
    }
    void pull(){
        sum = lc->sum + rc->sum;
    }
    void update( int ql, int qr, int v ){ // when v == 0, initializes [ ql, qr ) to 0
        if( qr <= lb or rb <= ql ) return;
        if( ql <= lb and rb <= qr ){
            if( v == 0 ){
                if( add_tag ) push();
                zero_tag = 1;
                sum = add_tag = 0;
                return;
            }
            if( zero_tag ) push();
            sum += v * ( rb - lb );
            add_tag += v;
            return;
        }
        push();
        lc->update( ql, qr, v );
        rc->update( ql, qr, v );
        pull();
    }
    int query( int ql, int qr ){
        if( qr <= lb or rb <= ql ) return 0;
        if( ql <= lb and rb <= qr ) return sum;
        push();
        int res = lc->query( ql, qr ) + rc->query( ql, qr );
        pull();
        return res;
    }
} *root[ 26 ];

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

void solve(){
    int N, Q; cin >> N >> Q;
    for( int i = 0; i < 26; ++i )
        root[ i ] = build_itvt( 0, N );

    string s; cin >> s;
    for( int i = 0; i < N; ++i )
        root[ s[ i ] - 'a' ]->update( i, i + 1, 1 );

    for( int i = 0; i < Q; ++i ){
        int ql, qr, k; cin >> ql >> qr >> k;
        --ql; // [ ql + 1, qr + 1 ] -> [ ql, qr )
        vp alpha;
        for( int a = 0; a < 26; ++a ){
            int c = k ? a : 25 - a;
            alpha.push_back( pii( c, root[ c ]->query( ql, qr ) ) );
            root[ c ]->update( ql, qr, 0 );
        }
        int used = 0;
        for( pii p : alpha ){
            int a = p.first;
            int v = p.second;
            root[ a ]->update( ql + used, ql + used + v, 1 );
            used += v;
        }
    }

    for( int i = 0; i < 26; ++i )
        for( int j = 0; j < N; ++j )
            if( root[ i ]->query( j, j + 1 ) )
                s[ j ] = ( char )( 'a' + i );

    cout << s << "\n";
}