【30.93%】【codeforces 558E】A Simple Task

time limit per test5 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
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
Note
First sample test explanation:
【题目链接】:http://codeforces.com/contest/558/problem/E

【题解】

计数排序.
因为数字的范围是1..26(把a..z看成是1..26);
则对于一个操作x,y；
如果想变成升序;
那么就看把x..y这个区间里面a..z的个数分别处理出来;
则从左到右放a..z;(有几个a就放几个a,有几个b就…按顺序就行);
为了快速获取x..y这个区间里面有多少个a..z;
可以用一个vector存每个字母在哪些位置出现过;
因为进行更改后原本位置在x..y这个区间的字母还是在x..y这个区间;
只不过“变得更密集了”;
所以vector始终会是单调递增。则用二分搞一下就能快速检索这个区间里面各个字母的个数了;
也可以用线段树搞。

【完整代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
#define pri(x) printf("%d",x)
#define prl(x) printf("%I64d",x)

typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

const int MAXN = 1e5+100;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);

int n,q;
char s[MAXN];
vector <int> g[28];

int main()
{
    //freopen("F:\rush.txt","r",stdin);
    rei(n);rei(q);
    scanf("%s",s+1);
    rep1(i,1,n)
        g[s[i]-'a'+1].pb(i);
    rep1(i,1,q)
    {
        int x,y,k;
        rei(x);rei(y);rei(k);
        if (k==1)
        {
            int now = x;
            rep1(j,1,26)
            {
                int ll = lower_bound(g[j].begin(),g[j].end(),x)-g[j].begin();
                int rr = upper_bound(g[j].begin(),g[j].end(),y)-g[j].begin()-1;
                rep1(k,ll,rr)
                    g[j][k] = now++;
            }
        }
        else
        {
            int now = x;
            rep2(j,26,1)
            {
                int ll = lower_bound(g[j].begin(),g[j].end(),x)-g[j].begin();
                int rr = upper_bound(g[j].begin(),g[j].end(),y)-g[j].begin()-1;
                rep1(k,ll,rr)
                    g[j][k] = now++;
            }
        }
    }
    rep1(j,1,26)
        {
            int len = g[j].size();
            char ke = 'a'+j-1;
            rep1(k,0,len-1)
                s[g[j][k]] =ke;
        }
    rep1(j,1,n)
        cout << s[j];
    cout << endl;
    return 0;
}