计数排序的原理，只要知道了有几个数比i小，就可以知道i的位置
这道题只有26个字母，搞26颗线段树，然后区间更新
#include <cstdio>
#include <cstring>
#include <algorithm> //using namespace std;
const int maxn = 1e5+; int N,Q;
char line[maxn]; #define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define root 1,1,N struct SegrTree{
int num[maxn<<];
int lazy[maxn<<];
void init()
{
memset(lazy,-,sizeof lazy);
}
void push_up(int rt)
{
num[rt] = num[rt<<] + num[rt<<|];
}
void push_down(int rt,int m)
{
if(lazy[rt] != -)
{
num[rt<<] = (m-(m>>))*lazy[rt] ;
num[rt<<|] = (m>>)*lazy[rt] ;
lazy[rt<<] = lazy[rt<<|] = lazy[rt];
lazy[rt] = -;
}
}
void build(int kind,int rt,int l,int r)
{
if(l == r)
{
num[rt] = line[l-]==kind+'a';
//if(line[l-1]=='c') printf("%c pos:%d \n",kind+'a',l);
return ;
}
int mid = (l+r)>>;
build(kind,lson);
build(kind,rson);
push_up(rt);
}
void update(int L,int R,int d,int rt,int l,int r)
{
if(L <= l && R >= r)
{
num[rt] = (r-l+)*d;
lazy[rt] = d;
return ;
}
push_down(rt,r-l+);
int mid = (l+r)>>;
if(L <= mid) update(L,R,d,lson);
if(R > mid) update(L,R,d,rson);
push_up(rt);
}
int query(int L,int R,int rt,int l,int r)
{
if(L <= l && R >= r)
{
return num[rt];
}
push_down(rt,r-l+);
int mid = (l+r)>>;
int res = ; if(R <= mid) res = query(L,R,lson);
else if(L > mid) res = query(L,R,rson);
else res = query(L,R,lson)+query(L,R,rson); push_up(rt);
return res;
}
}alpha[]; void sort(int l,int r,int k)
{
int pos,cnt;
if(k == )
{
pos = l;
for(int i=;i<;i++)
{
cnt = alpha[i].query(l,r,root);
//printf("[%d,%d]%c k:%d pos:%d cnt:%d\n",l,r,i+'a',k,pos,cnt);
if(cnt)
{
alpha[i].update(l,r,,root);
alpha[i].update(pos,pos+cnt-,,root);
pos += cnt;
}
}
}
else
{
pos = l;
for(int i=;i>=;i--)
{
cnt = alpha[i].query(l,r,root);
//printf("[%d,%d] %c k:%d pos:%d cnt:%d\n",l,r,i+'a',k,pos,cnt);
if(cnt)
{
alpha[i].update(l,r,,root);
alpha[i].update(pos,pos+cnt-,,root);
pos += cnt;
}
}
}
} int main()
{
//freopen("input.txt","r",stdin); scanf("%d%d",&N,&Q);
scanf("%s",line); for(int i=;i<;i++)
{
alpha[i].init();
alpha[i].build(i,root);
//printf("tot num:%c %d\n",i+'a',alpha[i].query(1,N,root));
}
//printf("c:%d c:%d\n",alpha[2].query(1,N,root),alpha[2].query(7,10,root));
for(int i=,l,r,k;i<Q;i++)
{
scanf("%d%d%d",&l,&r,&k);
sort(l,r,k);
}
for(int i=;i<=N;i++)
{
for(int j=;j<;j++) if(alpha[j].query(i,i,root))
{
printf("%c",'a'+j);
}
}
puts("");
}