E. A Simple Task

题目连接：

http://www.codeforces.com/contest/558/problem/E

Description

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.

Sample Input

10 5

abacdabcda

7 10 0

5 8 1

1 4 0

3 6 0

7 10 1

Sample Output

cbcaaaabdd

Hint

题意

给你n个字符，一共俩操作，l到r区间升序排序，l到r降序排序

字符集26.

让你输出最后的字符样子。

题解：

考虑计数排序，我们用线段树维护计数排序就好了，这样复杂度是26*q*logn

感觉自己智商还是涨了一波……

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e5+7;

struct Seg{

    typedef int SgTreeDataType;

    struct treenode

    {

        int L , R  ;

        SgTreeDataType sum , lazy;

        void update(SgTreeDataType v)

        {

            sum = (R-L+1)*v;

            lazy = v;

        }

    };

    treenode tree[maxn];

    inline void push_down(int o)

    {

        SgTreeDataType lazyval = tree[o].lazy;

        if(lazyval==-1)return;

        tree[2*o].update(lazyval) ; tree[2*o+1].update(lazyval);

        tree[o].lazy = -1;

    }

    inline void push_up(int o)

    {

        tree[o].sum = tree[2*o].sum + tree[2*o+1].sum;

    }

    inline void build_tree(int L , int R , int o)

    {

        tree[o].L = L , tree[o].R = R,tree[o].sum = 0,tree[o].lazy = -1;

        if (R > L)

        {

            int mid = (L+R) >> 1;

            build_tree(L,mid,o*2);

            build_tree(mid+1,R,o*2+1);

        }

    }

    inline void update(int QL,int QR,SgTreeDataType v,int o)

    {

        int L = tree[o].L , R = tree[o].R;

        if (QL <= L && R <= QR) tree[o].update(v);

        else

        {

            push_down(o);

            int mid = (L+R)>>1;

            if (QL <= mid) update(QL,QR,v,o*2);

            if (QR >  mid) update(QL,QR,v,o*2+1);

            push_up(o);

        }

    }

    inline SgTreeDataType query(int QL,int QR,int o)

    {

        int L = tree[o].L , R = tree[o].R;

        if (QL <= L && R <= QR) return tree[o].sum;

        else

        {

            push_down(o);

            int mid = (L+R)>>1;

            SgTreeDataType res = 0;

            if (QL <= mid) res += query(QL,QR,2*o);

            if (QR > mid) res += query(QL,QR,2*o+1);

            push_up(o);

            return res;

        }

    }

}T[26];

char s[maxn];

int cnt[26];

int main()

{

    int n,q;

    scanf("%d%d",&n,&q);

    scanf("%s",s+1);

    for(int i=0;i<26;i++)

        T[i].build_tree(1,n,1);

    for(int i=1;i<=n;i++)

        T[s[i]-'a'].update(i,i,1,1);

    for(int i=1;i<=q;i++)

    {

        int op,a,b;

        scanf("%d%d%d",&a,&b,&op);

        if(op==1)

        {

            for(int i=0;i<26;i++)

                cnt[i]=T[i].query(a,b,1);

            for(int i=0;i<26;i++)

                T[i].update(a,b,0,1);

            int l=a;

            for(int i=0;i<26;i++)

                T[i].update(l,l+cnt[i]-1,1,1),l+=cnt[i];

        }

        else

        {

            for(int i=25;i>=0;i--)

                cnt[i]=T[i].query(a,b,1);

            for(int i=25;i>=0;i--)

                T[i].update(a,b,0,1);

            int l=a;

            for(int i=25;i>=0;i--)

                T[i].update(l,l+cnt[i]-1,1,1),l+=cnt[i];

        }

    }

    for(int i=1;i<=n;i++)

        for(int j=0;j<26;j++)

            if(T[j].query(i,i,1))

                printf("%c",j+'a');

    return 0;

}

巴特西

Codeforces Round #312 (Div. 2) E. A Simple Task 线段树