E. 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.Sample test(s)
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: 题意，给一段字符串。然后一系列改动i,j之间的字符串从小到大排序，或从大到小排序。维护26的线段树。i,j改动。仅仅须要查询一个a - z的个数，按计数排序的原理，更新一下线段树就能够了。总的复杂度为o(26 * q * log(n));速度有点慢，用伸展树应该快些。由于是成段更新，所以要用延时标记，记-1不更新，0全置0，1全置1，仅仅有这点小技巧就能够了。#define N 100005#define M 100005#define maxn 205#define SZ 26#define MOD 1000000000000000007#define lson (now<<1)#define rson (now<<1|1)int n,q,ss,ee,k,num[SZ];char str[N];struct node{ int c,sum,l,r;};node tree[SZ][N*4];void pushDown(int tn,int now){ if(tree[tn][now].c != -1){ tree[tn][lson].c = tree[tn][rson].c = tree[tn][now].c; tree[tn][lson].sum = tree[tn][lson].c*(tree[tn][lson].r-tree[tn][lson].l + 1); tree[tn][rson].sum = tree[tn][rson].c*(tree[tn][rson].r-tree[tn][rson].l + 1); tree[tn][now].c = -1; }}void pushUp(int tn,int now){ tree[tn][now].sum = tree[tn][lson].sum + tree[tn][rson].sum ;}void buildTree(int l,int r,int now){ FI(SZ) tree[i][now].c = -1,tree[i][now].l = l,tree[i][now].r = r,tree[i][now].sum = 0; if(l >= r){ return ; } int mid = (l+r)>>1; buildTree(l,mid,lson); buildTree(mid+1,r,rson);}void updateTree(int l,int r,int now,int s,int e,int tn,int c){ if(s <= l && e>= r){ tree[tn][now].c = c; tree[tn][now].sum = tree[tn][now].c*(tree[tn][now].r - tree[tn][now].l + 1); return ; } pushDown(tn,now); int mid = (l+r)>>1; if(s <= mid) updateTree(l,mid,lson,s,e,tn,c); if(e > mid) updateTree(mid+1,r,rson,s,e,tn,c); pushUp(tn,now);}int queryTree(int l,int r,int now,int s,int e,int tn){ if(s <= l && e>= r){ return tree[tn][now].sum; } pushDown(tn,now); int mid = (l+r)>>1; int ans = 0; if(s <= mid) ans += queryTree(l,mid,lson,s,e,tn); if(e > mid) ans += queryTree(mid+1,r,rson,s,e,tn); pushUp(tn,now); return ans;}void outputStr(){ FI(n){ FJ(SZ){ if(queryTree(1,n,1,i+1,i+1,j)){ printf("%c",j+'a'); break; } } } printf("\n");}int main(){ while(S2(n,q)!=EOF) { SS(str); buildTree(1,n,1); FI(n){ updateTree(1,n,1,i+1,i+1,str[i] - 'a',1); } FI(q){ S2(ss,ee);S(k); FJ(SZ) num[j] = queryTree(1,n,1,ss,ee,j); FJ(SZ) updateTree(1,n,1,ss,ee,j,0); if(k){ int sum = 0; FJ(SZ){ if(num[j]) updateTree(1,n,1,ss + sum,ss + sum + num[j] - 1,j,1); sum += num[j]; } } else { int sum = 0; for(int j = SZ - 1;j>=0;j--){ if(num[j]) updateTree(1,n,1,ss + sum,ss + sum + num[j] - 1,j,1); sum += num[j]; } } } outputStr(); } return 0;}