题目链接:http://codeforces.com/problemset/problem/558/E
给一个字符串,每次对一个区间内的子串进行升序或者降序的排列,问最后字符串什么样子。
对于字符串排序,计数排序是比一般的排序要快的,但是仍然不能解决本问题。
建立26个线段树,用于统计某个字符在某个区间的情况。
那么如果对【L,R】排序,则先统计所有字符在其中的情况,并且清空该区间,根据每个字符的数量,从a到z去填充应该在的小区间。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctime>
#include <numeric>
#include <cassert> using namespace std; const int N=1e5+; char s[N]; struct SegmentTree {
#define M N*4
int val[M];
int flag[M];
void up(int rt) {
val[rt]=val[rt<<]+val[rt<<|];
}
void build(int l,int r,int rt) {
if (l==r) {
val[rt]=;
flag[rt]=-;
return;
}
int m=(l+r)>>;
build(l,m,rt<<);
build(m+,r,rt<<|);
up(rt);
}
void down(int rt,int m=) {
if (flag[rt]!=-) {
flag[rt<<]=flag[rt];
flag[rt<<|]=flag[rt];
if (flag[rt]==){
val[rt<<]=m-(m>>);
val[rt<<|]=(m>>);
}
else {
val[rt<<]=;
val[rt<<|]=;
}
flag[rt]=-;
}
}
void update(int p,int c,int l,int r,int rt) {
if (l==r) {
val[rt]=c;
return;
}
down(rt,r-l+);
int m=(l+r)>>;
if (p<=m)
update(p,c,l,m,rt<<);
else
update(p,c,m+,r,rt<<|);
up(rt);
}
void update(int L,int R,bool c,int l,int r,int rt) {
if (L<=l&&r<=R) {
val[rt]=c?(r-l+):;
flag[rt]=c;
return;
}
down(rt,r-l+);
int m=(l+r)>>;
if (L<=m) update(L,R,c,l,m,rt<<);
if (R>m) update(L,R,c,m+,r,rt<<|);
up(rt);
}
int query(int p,int l,int r,int rt) {
if (l==r) {
return val[rt];
}
down(rt,r-l+);
int m=(l+r>>);
if (p<=m) return query(p,l,m,rt<<);
else return query(p,m+,r,rt<<|);
}
int query(int L,int R,int l,int r,int rt) {
if (L<=l&&r<=R) {
return val[rt];
}
down(rt,r-l+);
int m=(l+r)>>;
int ret=;
if (L<=m) ret+=query(L,R,l,m,rt<<);
if (R>m) ret+=query(L,R,m+,r,rt<<|);
return ret;
}
#undef M
}seg[]; int main() {
int n,q;
scanf("%d %d",&n,&q);
scanf("%s",s+);
for (int i=;i<;i++)
seg[i].build(,n,);
for (int i=;i<=n;i++) {
int p=s[i]-'a';
seg[p].update(i,,,n,);
//cout<<p<<" xxx"<<endl;
}
while (q--) {
int l,r,t;
scanf("%d %d %d",&l,&r,&t);
int cnt[];
for (int i=;i<;i++) {
cnt[i]=seg[i].query(l,r,,n,);
if (cnt[i]>){
seg[i].update(l,r,,,n,);
}
}
if (t==) {
for (int i=;i<;l+=cnt[i++]){
if (cnt[i]==) continue;
seg[i].update(l,l+cnt[i]-,,,n,);
}
}
else {
for (int i=;i>=;l+=cnt[i--]){
if (cnt[i]==) continue;
seg[i].update(l,l+cnt[i]-,,,n,);
}
}
}
for (int i=;i<=n;i++) {
for (int j=;j<;j++){
if (seg[j].query(i,,n,)) {
s[i]='a'+j;
break;
}
}
}
s[n+]=;
printf("%s\n",s+);
return ;
}