题目链接 A Simple Task
题意 给出一个小写字母序列和若干操作。每个操作为对给定区间进行升序排序或降序排序。
考虑权值线段树。
建立26棵权值线段树。每次操作的时候先把26棵线段树上的所有在该区间内的信息清空。
然后再通过类似计数排序的方式从左往右（或从右往左）依次塞进去。
#include <bits/stdc++.h>using namespace std;#define rep(i, a, b)for (int i(a); i <= (b); ++i)
#define dec(i, a, b)for (int i(a); i >= (b); --i)
#define lsi << 1
#definersi << 1 | 1
#define lsonls, L, mid
#definersonrs, mid + 1, Rtypedef long long LL;const int N = 1e5 + 10;struct node{
int sum[2];
int len;
} s[27][N * 3];int n, q;
int a[N];
char st[N];
int dc[27][N * 3];
int f[27];inline node update(const node &x, const node &y){
node ret;
ret.len = x.len + y.len;
rep(i, 0, 1) ret.sum[i] = x.sum[i] + y.sum[i];
return ret;
}void build(int cnt, int i, int L, int R){
if (L == R){
int z = a[L] == cnt;
s[cnt][i].len = 1;
s[cnt][i].sum[z] = 1;
s[cnt][i].sum[z ^ 1] = 0;
dc[cnt][i] = -1;
return;
}int mid = (L + R) >> 1;
build(cnt, lson);
build(cnt, rson);
s[cnt][i] = update(s[cnt][ls], s[cnt][rs]);
dc[cnt][i] = -1;
}inline void paintcover(int cnt, int i, int z){
dc[cnt][i] = z;
s[cnt][i].sum[z] = s[cnt][i].len;
s[cnt][i].sum[z ^ 1] = 0;
}inline void pushdown(int cnt, int i){
if (~dc[cnt][i]){
paintcover(cnt, ls, dc[cnt][i]);
paintcover(cnt, rs, dc[cnt][i]);
dc[cnt][i] = -1;
}
}void cover(int cnt, int i, int L, int R, int l, int r, int z){
if (l <= L && R <= r){
paintcover(cnt, i, z);
return;
}pushdown(cnt, i);
int mid = (L + R) >> 1;
if (l <= mid) cover(cnt, lson, l, r, z);
if (r > mid) cover(cnt, rson, l, r, z);
s[cnt][i] = update(s[cnt][ls], s[cnt][rs]);
}int query(int cnt, int i, int L, int R, int l, int r){
int ret = 0;
if (l <= L && R <= r) return s[cnt][i].sum[1];
int mid = (L + R) >> 1;
pushdown(cnt, i);
if (l <= mid) ret += query(cnt, lson, l, r);
if (r > mid) ret += query(cnt, rson, l, r);
return ret;
}int main(){scanf("%d%d", &n, &q);
scanf("%s", st + 1);
rep(i, 1, n) a[i] = (int)st[i] - 96;
rep(i, 1, 26) build(i, 1, 1, n);while (q--){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
rep(i, 1, 26) f[i] = query(i, 1, 1, n, x, y);
rep(i, 1, 26) cover(i, 1, 1, n, x, y, 0);
if (z){
int pos = x;
rep(i, 1, 26) if (f[i]){
cover(i, 1, 1, n, pos, pos + f[i] - 1, 1);
pos += f[i];
}
}else{
int pos = x;
dec(i, 26, 1) if (f[i]){
cover(i, 1, 1, n, pos, pos + f[i] - 1, 1);
pos += f[i];
}
}
}rep(i, 1, n){
rep(j, 1, 26) if (query(j, 1, 1, n, i, i)){
putchar(j + 96);
break;
}
}putchar(10);
return 0;
}
