题目链接：http://codeforces.com/contest/558/problem/E
题意：有一串字符串，有两个操作：1操作是将l到r的字符串升序排序，0操作是降序排序。
题解：建立26棵线段树，类似计数排序思想。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + ;
struct SegTree {
int lazy[], sum[], l, r;
}T[N << ];
int a[][N]; void pushup(int p, int c) {
T[p].sum[c] = T[p << ].sum[c] + T[(p << )|].sum[c];
} void pushdown(int p, int c) {
if(T[p].lazy[c] != -) {
T[p << ].sum[c] = T[p].lazy[c]*(T[p << ].r - T[p << ].l + );
T[(p << )|].sum[c] = T[p].lazy[c]*(T[(p << )|].r - T[(p << )|].l + );
T[p << ].lazy[c] = T[(p << )|].lazy[c] = T[p].lazy[c];
T[p].lazy[c] = -;
}
} void build(int p, int c, int l, int r) {
int mid = (l + r) >> ;
T[p].l = l, T[p].r = r, T[p].lazy[c] = -;
if(l == r) {
T[p].sum[c] = a[c][l];
return ;
}
build(p << , c, l, mid);
build((p << )|, c, mid + , r);
pushup(p, c);
} int query(int p, int c, int l, int r) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
return T[p].sum[c];
}
pushdown(p, c);
if(r <= mid) {
return query(p << , c, l, r);
} else if(l > mid) {
return query((p << )|, c, l, r);
} else {
return query(p << , c, l, mid) + query((p << )|, c, mid + , r);
}
pushup(p, c);
} void update(int p, int c, int l, int r, int val) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
T[p].lazy[c] = val;
T[p].sum[c] = val * (r - l + );
return ;
}
pushdown(p, c);
if(r <= mid) {
update(p << , c, l, r, val);
} else if(l > mid) {
update((p << )|, c, l, r, val);
} else {
update(p << , c, l, mid, val), update((p << )|, c, mid + , r, val);
}
pushup(p, c);
}
char str[N]; int main()
{
int n, m;
scanf("%d %d", &n, &m);
scanf("%s", str);
for(int i = ; i < n; ++i) {
a[str[i] - 'a'][i + ] = ;
}
for(int i = ; i < ; ++i) {
build(, i, , n);
}
while(m--) {
int l, r, c;
scanf("%d %d %d", &l, &r, &c);
if(c) {
int x = l, y = r;
for(int i = ; i < ; ++i) {
if(x > y)
break;
int num = query(, i, l, r);
if(!num)
continue;
update(, i, l, r, );
update(, i, x, x + num - , );
x = x + num;
}
} else {
int x = l, y = r;
for(int i = ; i >= ; --i) {
if(x > y)
break;
int num = query(, i, l, r);
if(!num)
continue;
update(, i, l, r, );
update(, i, x, x + num - , );
x = x + num;
}
}
}
for(int i = ; i <= n; ++i) {
for(int j = ; j < ; ++j) {
if(query(, j, i, i)) {
putchar(char(j + 'a'));
break;
}
}
}
putchar('\n');
return ;
}