CodeForces - 558E A Simple Task （计数排序 线段树）

This task is very simple. Given a string S of length n and q queries each query is on the format i j k which means sort the substring consisting of the characters from i to j in non-decreasing order if k = 1 or in non-increasing order if k = 0.

Output the final string after applying the queries.

Input
The first line will contain two integers n, q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000), the length of the string and the number of queries respectively.

Next line contains a string S itself. It contains only lowercase English letters.

Next q lines will contain three integers each i, j, k (1 ≤ i ≤ j ≤ n, ).

Output
Output one line, the string S after applying the queries.

Examples
Input
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
Output
cbcaaaabdd
Input
10 1
agjucbvdfk
1 10 1
Output
abcdfgjkuv

题意很简单，就是给你个字符串，然后又q次操作，每次操作有i,j,k三个值，如果k为0，就把i,j区间的字符降序排序，如果k = 1,就将i，j区间的字符串升序排序，最后输出这个字符串。下标从1开始。

直接暴力显然会超时，这个题因为只有26个小写字母，所以我们可以利用区间查询出这个区间每个字符的个数，先把这个区间所有字符的个数都更新为0，即相当于删去所有字符。然后再按照升或降的顺序从开头存放，即从新填放，这里面对于区间的操作我们就用到了线段树。

代码如下:

#include<bits/stdc++.h>

using namespace std;
#define lson (k*2)
#define rson (k*2+1)
const int MAX = 100010;
const int MAX_V = 28;
class Node{
public:
    int l,r,v[MAX_V];
    Node();
    int mid(){
        return (l+r)/2;
    }
    int len(){
        return r-l+1;
    }
};
int Lazy[MAX*4][MAX_V];
int N,Q;
char str[MAX];
Node tree[MAX*4];
void PushUp(int k,int id){
    tree[k].v[id] = tree[lson].v[id] + tree[rson].v[id];
}
void PushDown(int k,int id){
    if(Lazy[k][id] != -1){
        int value = Lazy[k][id];
        tree[lson].v[id] = tree[lson].len()*value;
        tree[rson].v[id] = tree[rson].len()*value;
        Lazy[lson][id] = value;
        Lazy[rson][id] = value;
    }
    Lazy[k][id] = -1;
}
void Build(int L,int R,int k){
    tree[k].l = L;
    tree[k].r = R;
    if(L == R){
        int id = str[L]-'a';
        tree[k].v[id] = 1;
        return;
    }
    int mid = (L+R)/2;
    Build(L,mid,lson);
    Build(mid+1,R,rson);
    for(int i=0;i<26;++i)
        PushUp(k,i);
}
void Update(int L,int R,int add,int k,int id){
    if(L <= tree[k].l && tree[k].r <= R){
        tree[k].v[id] = add*tree[k].len();
        Lazy[k][id] = add;
        return;
    }
    PushDown(k,id);
    int mid = tree[k].mid();
    if(L <= mid)    Update(L,R,add,lson,id);
    if(R > mid) Update(L,R,add,rson,id);
    PushUp(k,id);
}
int Query(int L,int R,int k,int id){
    if(L <= tree[k].l && tree[k].r <= R)
        return tree[k].v[id];
    PushDown(k,id);
    int res = 0;
    int mid = tree[k].mid();
    if(L <= mid)    res += Query(L,R,lson,id);
    if(R > mid)     res += Query(L,R,rson,id);
    return res;
}
void Display(){
    for(int i=1;i<=N;++i){
        for(int id=0;id<26;++id){
            if(Query(i,i,1,id)){
                printf("%c",'a'+id);
            }
        }
    }
    printf("\n");
}
void Show(int *bas){
    for(int id=0;id<26;++id){
        printf("%d ",bas[id]);
    }
    printf("\n");
}
int main(void){
    //这里要把lzay设置为-1，因为更新值可能为0，注意。
    memset(Lazy,-1,sizeof(Lazy));
    scanf("%d%d",&N,&Q);
    scanf("%s",str+1);
    Build(1,N,1);
    int u,v,w;
    int bas[MAX_V];//存储每个字符的个数
    for(int i=1;i<=Q;++i){
        scanf("%d%d%d",&u,&v,&w);
        if(w == 0){
            //查询该区间每个字符的个数。
            for(int id=0;id<26;++id){
                bas[id] = Query(u,v,1,id);
                Update(u,v,0,1,id);
            }
            int l=u,r;
            //0表示降序，即从后往前更新对应区间的字符。
            for(int id=25;id>=0;--id){
                if(bas[id]){
                    r = l+bas[id]-1;
                    Update(l,r,1,1,id);
                    l += bas[id];
                }
            }
        }
        else{
            for(int id=0;id<26;++id){
                bas[id] = Query(u,v,1,id);
                Update(u,v,0,1,id);
            }
            int l=u,r;
            for(int id=0;id<26;++id){
                if(bas[id]){
                    r = l + bas[id]-1;
                    Update(l,r,1,1,id);
                    l += bas[id];
                }
            }
        }

    }
    Display();
    return 0;
}
Node::Node(){
    l = r = 0;
    memset(v,0,sizeof(v));
}