CodeForces - 558 E. A Simple Task 문자열 구간 정렬 (계수 정렬 + 26 개의 선분 트 리 유지 보수)

제목 링크http://codeforces.com/problemset/problem/558/E
Time limit ：5000 ms Memory limit ： 524288 kB
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, ).(0<=k<=1)
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
Note
First sample test explanation:
abacdabcda->abacdadcba abacdadcba->abacacddba abacacddba->cbaaacddba cbaaacddba->cbcaaaddba cbcaaaddba->cbcaaaabdd
제목 대의: 문자열 을 하나 드 리 겠 습 니 다. 번 호 는 1 부터 n 까지 q 번 으로 작 동 합 니 다. 매번 x, y, id 로 작 동 합 니 다. id 가 0 이면 구간 [x, y] 의 내림차 순 으로 정렬 합 니 다. 그렇지 않 으 면 오름차 순 으로 정렬 합 니 다.
우 리 는 먼저 STL 대 법 폭력 을 일 으 킬 수 있 습 니 다. test 9, is 까지 달 릴 수 있 습 니 다.sorted 는 좋 은 물건 입 니 다:

#include 
using namespace std;

const int mac=1e5+10;

char s[mac];
int a[mac];

bool cmpde(int x,int y){return x>y;}
bool cmpin(int x,int y){return x<y;}

int main()
{
    int n,q;
    scanf ("%d%d",&n,&q);
    scanf ("%s",s+1);
    for (int i=1; i<=n; i++) a[i]=s[i]-'a';
    while (q--){
        int l,r,id;
        scanf ("%d%d%d",&l,&r,&id);
        if (id==0) {
            bool yes = is_sorted(a + l, a + 1 + r, cmpde);
            if (!yes) sort(a+l,a+1+r,cmpde);
        }
        else {
            bool yes=is_sorted(a+l,a+1+r,cmpin);
            if (!yes) sort(a+l,a+1+r,cmpin);
        }
    }
    for (int i=1; i<=n; i++)
            printf ("%c",a[i]+'a');
    printf ("
");
    return 0;
}

그리고 생각해 보면 우 리 는 O (n) 의 계수 로 정렬 할 수 있다. 왜냐하면 이곳 에 필요 한 공간 이 매우 작 기 때문이다.모든 선분 트 리 는 알파벳 을 유지 하고 문의 하고 수정 할 때 0 에서 25 까지 한 번 씩 갑 니 다.마지막 복잡 도 는 O (26 * q * logn) 입 니 다.쓰기 편 하도록 우 리 는 선분 나무의 조작 과 선분 나 무 를 구조 체 안에 넣 어 포장 할 수 있다.
다음은 AC 코드 입 니 다.

#include 
using namespace std;

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define debug printf ("**")

const int mac=1e5+10;

char s[mac];
int a[mac];

struct Tree
{
    int sum,f;
};

struct node
{
    Tree tree[mac<<2];

    void build(int l,int r,int rt,int val)
    {
        tree[rt].f=-1;
        if (l==r){
            if (a[l]==val) tree[rt].sum=1;
            else tree[rt].sum=0;
            return;
        }
        int mid=(l+r)>>1;
        build(lson,val);build(rson,val);
        tree[rt].sum=tree[ls].sum+tree[rs].sum;
    }

    void pushdown(int l,int r,int rt)
    {
        int mid=(l+r)>>1;
        tree[ls].f=tree[rs].f=tree[rt].f;
        tree[ls].sum=(mid-l+1)*tree[rt].f;
        tree[rs].sum=(r-mid)*tree[rt].f;
        tree[rt].f=-1;
    }

    void update(int l,int r,int rt,int L,int R,int val)
    {
        if (l>=L && r<=R) {
            tree[rt].sum=(r-l+1)*val;
            tree[rt].f=val;
            return;
        }
        int mid=(l+r)>>1;
        if (tree[rt].f!=-1) pushdown(l,r,rt);
        if (mid>=L) update(lson,L,R,val);
        if (mid<R) update(rson,L,R,val);
        tree[rt].sum=tree[ls].sum+tree[rs].sum;
    }

    int query(int l,int r,int rt,int L,int R)
    {
        int sum=0;
        if (l>=L && r<=R) return tree[rt].sum;
        int mid=(l+r)>>1;
        if (tree[rt].f!=-1) pushdown(l,r,rt);
        if (mid>=L) sum+=query(lson,L,R);
        if (mid<R) sum+=query(rson,L,R);
        return sum;
    }
}sgtree[30];

int num[30];

int main()
{
    int n,q;
    scanf ("%d%d",&n,&q);
    scanf ("%s",s+1);
    for (int i=1; i<=n; i++) a[i]=s[i]-'a';
    for (int i=0; i<26; i++) sgtree[i].build(1,n,1,i);
    while (q--){
        int l,r,id;
        scanf("%d%d%d",&l,&r,&id);
        memset(num,0,sizeof num);
        for (int i=0; i<26; i++) {
            num[i] = sgtree[i].query(1, n, 1, l, r);//         
            sgtree[i].update(1, n, 1, l, r, 0);// i        [l,r]
        }
        if (id){//    
            for (int i=0; i<26; i++){
                if (!num[i]) continue;
                sgtree[i].update(1,n,1,l,l+num[i]-1,1);
                l+=num[i];//           
            }
        }
        else {//    
            for (int i=25; i>=0; i--){
                if (!num[i]) continue;
                sgtree[i].update(1,n,1,l,l+num[i]-1,1);
                l+=num[i];
            }
        }
    }
    for (int i=1; i<=n; i++){
        for (int j=0; j<26; j++){//      i       
            if (sgtree[j].query(1,n,1,i,i)) {
                printf ("%c",j+'a');
                break;
            }
        }
    }
    printf ("
");
    return 0;
}