Discription
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.
Example
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1
cbcaaaabdd
10 1
agjucbvdfk
1 10 1
abcdfgjkuv
Note
First sample test explanation:
大概是第一次坐到沙发hhh
可以发现只有26个小写英文，那么就不难了，就是一个常数*26的带标记线段树。。。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define maxn 100005
using namespace std;
struct node{
int sum[28];
int tag;
node operator +(const node& u)const{
node r; r.tag=0;
for(int i=1;i<27;i++) r.sum[i]=sum[i]+u.sum[i];
return r;
}
}a[maxn<<2|1];
int le,ri,opt,w;
int n,m,v,num[30];
char s[maxn];
void build(int o,int l,int r){
if(l==r){
a[o].sum[s[l]-‘a‘+1]++;
return;
}
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1;
build(lc,l,mid),build(rc,mid+1,r);
a[o]=a[lc]+a[rc];
}
inline void tol(int o,int tmp,int len){
memset(a[o].sum,0,sizeof(a[o].sum));
a[o].sum[tmp]=len;
a[o].tag=tmp;
}
inline void pushdown(int o,int l,int r){
if(a[o].tag){
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1;
tol(lc,a[o].tag,mid-l+1);
tol(rc,a[o].tag,r-mid);
a[o].tag=0;
}
}
void update(int o,int l,int r){
if(l>=le&&r<=ri){
tol(o,v,r-l+1);
return;
}
pushdown(o,l,r);
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1;
if(le<=mid) update(lc,l,mid);
if(ri>mid) update(rc,mid+1,r);
a[o]=a[lc]+a[rc];
}
int query(int o,int l,int r){
if(l>=le&&r<=ri) return a[o].sum[v];
pushdown(o,l,r);
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1,an=0;
if(le<=mid) an+=query(lc,l,mid);
if(ri>mid) an+=query(rc,mid+1,r);
return an;
}
void print(int o,int l,int r){
if(l==r){
for(int i=1;i<27;i++) if(a[o].sum[i]){
putchar(i-1+‘a‘);
break;
}
return;
}
pushdown(o,l,r);
int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1;
print(lc,l,mid);
print(rc,mid+1,r);
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",s+1);
build(1,1,n);
while(m--){
scanf("%d%d%d",&le,&ri,&opt);
memset(num,0,sizeof(num));
for(v=1;v<=26;v++) num[v]=query(1,1,n);
if(opt){
int pre=le,nxt;
for(int i=1;i<=26;i++) if(num[i]){
nxt=pre+num[i]-1,v=i;
le=pre,ri=nxt;
update(1,1,n);
pre=nxt+1;
}
}
else{
int pre=le,nxt;
for(int i=26;i;i--) if(num[i]){
nxt=pre+num[i]-1,v=i;
le=pre,ri=nxt;
update(1,1,n);
pre=nxt+1;
}
}
// print(1,1,n);
}
print(1,1,n);
return 0;
}