Given a string S ,the length is n ,and It contains only lowercase English letters.Also given q queries each query is on the format i j k ,that means sort the substring consisting of the characters from i to j , do it if k=1 non-decreasing order and if k=0 in non-increasing order. Output the final string after all queries.
First line contain two integers n, q (1 ≤ n ≤ 105 105, 0 ≤ q ≤ 50 000), for the string’s length and the number of queries. Second line contains a string S. Next q lines will contain three integers each i, j, k (1 ≤ i ≤ j ≤ n, k=1 or k=0 ).
Output one line, the string S after all queries.
题意是每一次可以对区间[L,R]里的数进行排序，在所有的操作做完之后输出最终的序列
第一想法肯定是线段树嘛，然后我想的是给区间打上这一段是升序还是逆序的lazy标记，最后输出答案
这个想法看上去很好，但是实际上是不行的，因为区间排序这个操作并不能很好的维护我们需要的值。
意思就是普通的区间加，和区间赋值，在实际储存的时候可能是分成若干段区间，在每个区间上都有一个lazy标记，但是排序分成若干段之后，没办法保证和在整个区间上排序是等价的，因此我就不会做了。。。。。。
正解是排序这一个操作可以转化为先查询后赋值，也就说先查询区间[L,R]上的每个字母出现的个数，然后按照相应的顺序给一段一段地给区间赋值相应的字母，这就要求我们的线段树维护26个值，代表26个字母的出现次数。只要这一点想到了，那基本上和普通的区间赋值，区间查询就没有什么很大的区别了。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define mid ((le+ri)>>1) #define lson (node<<1) #define rson (node<<1|1) #define lc lson,le,mid #define rc rson,mid+1,ri #define sc node,le,ri using namespace std; const int maxm=1E5+10; int n,q,ord,st[maxm*5][26],lazy[maxm*5],x,y,val,res[26]; void init(int node=1,int le=1,int ri=n),query(int node=1,int le=1,int ri=n), update(int node=1,int le=1,int ri=n),pushdown(int node,int le,int ri), pushup(int node),getans(int node=1,int le=1,int ri=n); char str[maxm]; int main(){ while(scanf("%d%d",&n,&q)!=EOF){ scanf("%s",str); init(); while(q--){ scanf("%d%d%d",&x,&y,&ord); memset(res,0,sizeof res); query(); if(ord!=1){ for(int i=25;i>=0;--i) if(res[i]){ y=x+res[i]-1,val=i; update(); x+=res[i]; } }else{ for(int i=0;i<26;++i) if(res[i]){ y=x+res[i]-1,val=i; update(); x+=res[i]; } } } getans(); printf("\n"); } return 0; } void pushdown(int node, int le, int ri){ if(lazy[node]!=-1){ lazy[lson]=lazy[rson]=lazy[node]; memset(st[lson],0,sizeof st[lson]); memset(st[rson],0,sizeof st[rson]); st[lson][lazy[node]]=mid-le+1; st[rson][lazy[node]]=ri-mid; lazy[node]=-1; } } void pushup(int node){ for(int i=0;i<26;++i) st[node][i]=st[lson][i]+st[rson][i]; } void init(int node, int le, int ri){ lazy[node]=-1; if(le==ri){ memset(st[node],0,sizeof st[node]); st[node][str[le-1]-'a']=1; }else{ init(lc); init(rc); pushup(node); } } void update(int node,int le,int ri){ if(ri<x||le>y)return; if(x<=le&&ri<=y){ lazy[node]=val; memset(st[node],0,sizeof st[node]); st[node][val]=ri-le+1; }else{ pushdown(sc); update(lc); update(rc); pushup(node); } } void getans(int node, int le, int ri){ if(le==ri){ for(int i=0;i<26;++i) if(st[node][i]){ printf("%c",i+'a'); return; } }else{ pushdown(sc); getans(lc); getans(rc); } } void query(int node,int le,int ri){ if(ri<x||le>y)return; if(x<=le&&ri<=y){ for(int i=0;i<26;++i) res[i]+=st[node][i]; }else{ pushdown(sc); query(lc); query(rc); } }
