# TIOJ 1952 小向的試煉 3-3：鑰匙 ( Segment Tree, Tags )

1952 - 小向的試煉 3-3：鑰匙(Key) | TIOJ INFOR Online Judge

O( N lg N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e5;

int N, M;
string seq;

struct Segment_Tree{
int sum[ MAXN << 3 ];
int tag[ MAXN << 3 ];
int ctag[ MAXN << 3 ];
void push( int t, int lb, int rb ){
if( ctag[ t ] ){
ctag[ t << 1 ] = ctag[ t << 1 | 1 ] = 1;
sum[ t << 1 ] = sum[ t << 1 | 1 ] = 0;
tag[ t << 1 ] = tag[ t << 1 | 1 ] = 0;
ctag[ t ] = 0;
}
int mid = lb + rb >> 1;
sum[ t << 1 ] += ( mid - lb ) * tag[ t ];
tag[ t << 1 ] += tag[ t ];
sum[ t << 1 | 1 ] += ( rb - mid ) * tag[ t ];
tag[ t << 1 | 1 ] += tag[ t ];
tag[ t ] = 0;
}
void pull( int t ){
sum[ t ] = sum[ t << 1 ] + sum[ t << 1 | 1 ];
}
void update( int t, int lb, int rb, int ql, int qr, int v ){
if( qr <= lb or rb <= ql ) return;
if( ql <= lb and rb <= qr ){
if( ctag[ t ] ){
if( lb + 1 < rb ){
ctag[ t << 1 ] = ctag[ t << 1 | 1 ] = 1;
sum[ t << 1 ] = sum[ t << 1 | 1 ] = 0;
tag[ t << 1 ] = tag[ t << 1 | 1 ] = 0;
}
ctag[ t ] = 0;
}
sum[ t ] += ( rb - lb ) * v;
tag[ t ] += v;
return;
}
push( t, lb, rb );
int mid = lb + rb >> 1;
update( t << 1, lb, mid, ql, qr, v );
update( t << 1 | 1, mid, rb, ql, qr, v );
pull( t );
}
int query( int t, int lb, int rb, int ql, int qr ){
if( qr <= lb or rb <= ql ) return 0;
if( ql <= lb and rb <= qr ) return sum[ t ];
push( t, lb, rb );
int mid = lb + rb >> 1;
int res = query( t << 1, lb, mid, ql, qr )
+ query( t << 1 | 1, mid, rb, ql, qr );
pull( t );
return res;
}
void clear( int t, int lb, int rb, int ql, int qr ){
if( qr <= lb or rb <= ql ) return;
if( ql <= lb and rb <= qr ){
ctag[ t ] = 1;
tag[ t ] = 0;
sum[ t ] = 0;
return;
}
push( t, lb, rb );
int mid = lb + rb >> 1;
clear( t << 1, lb, mid, ql, qr );
clear( t << 1 | 1, mid, rb, ql, qr );
pull( t );
}
} segt[ 26 ];

void build( int z, int t, int lb, int rb, const string &seq ){
if( lb + 1 == rb ){
segt[ z ].sum[ t ] = seq[ lb ] - 'a' == z;
return;
}
int mid = lb + rb >> 1;
build( z, t << 1, lb, mid, seq );
build( z, t << 1 | 1, mid, rb, seq );
segt[ z ].pull( t );
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> M;
cin >> seq;
for( int i = 0; i < 26; ++i ){
build( i, 1, 0, N, seq );
}
for( int i = 0; i < M; ++i ){
int ql, qr, k; cin >> ql >> qr >> k; --ql; // [ ql, qr )
vector< int > cnt( 26 );
for( int j = 0; j < 26; ++j ){
cnt[ j ] += segt[ j ].query( 1, 0, N, ql, qr );
segt[ j ].clear( 1, 0, N, ql, qr );
}
if( k == 0 ){
int lp = ql; // last puttable position
for( int j = 26 - 1; j >= 0; --j ){
segt[ j ].update( 1, 0, N, lp, lp + cnt[ j ], 1 );
lp += cnt[ j ];
}
} else{
int lp = ql;
for( int j = 0; j < 26; ++j ){
segt[ j ].update( 1, 0, N, lp, lp + cnt[ j ], 1 );
lp += cnt[ j ];
}
}
}
string ans;
for( int i = 0; i < N; ++i ){
for( int j = 0; j < 26; ++j ){
if( segt[ j ].query( 1, 0, N, i, i + 1 ) ){
ans += ( char ) ( 'a' + j );
break;
}
}
}
cout << ans << endl;
return 0;
}
```