codeforces 558 E. A Simple Task (线段树优化计数排序)
题意：给出一个字符串，仅由小写字母组成。现在给出q个操作，每个操作l,r,k三个参数，k=1表示把区间[l,r]变为升序排列，k=0表示把区间[l,r]变为降序排列。
思路：首先，最重要的一点是，由于只有26个字母，联想到计数排序。
对于字符集数目比较小情况，一定要想到计数排序。
对于字符集数目比较小情况，一定要想到计数排序。
对于字符集数目比较小情况，一定要想到计数排序。
那么我们回顾计数排序，不妨考虑升序排列的情况，是怎么做的呢？
做法是统计该区间中每种字符的个数，然后按照字符的大小，从小到大在区间上从左到右得放置每种字符。
大概是这样子：
1for(int j=x;j<=y;j++)
2 cnt[s[j] - 'a']++;
3ind = 0;
4for(int j=x;j<=y;j++)
5{
6 while(cnt[ind] == 0)
7 ind++;
8 s[j] = ind + 'a';
9 cnt[ind]--;
10}
然而这个复杂度每次是o(n)的。。。
我们需要用线段树来优化计数排序的过程。。。
思考计数排序其实分为两个过程：
一是统计某区间中每个字符的个数。
二是将字符按照字符的大小顺序重新放回区间。
我们可以建26棵线段树，一种字母对应一棵。
对于过程一，我们可以直接query.
对于过程2，由于相同的字母总是相邻在一起的，因此可以用线段树成段更新来优化，也就是lazy标记。
tree[id][rt]表示第id棵线段树对应的区间中字母id+'a'-1的个数。
lazy[id][rt]三种值，-1表示没有标记，0表示重置标记，1表示被某种字母覆盖的标记。（重置的意思是，该区间被排序了，但是还不确定该区间上字母是哪些）
输出的时候，对于某个位置，只要query到26个字母中值不为0的那个输出就好了。
总的复杂度：O(26qlgn)
代码注释中还有部分细节和理解
1/* ***********************************************
2Author :111qqz
3Created Time :2016年10月04日 星期二 23时59分11秒
4File Name :code/cf/problem/558E.cpp
5 ************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <deque>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <bitset>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32const int N=1E5+7;
33int tree[27][N<<2];//26棵线段树，表示26个字母在对应区间中的个数。
34int lazy[27][N<<2];//lazy存储的是某段区间是否被某个字母覆盖. -1表示初始没有标记，0表示该区间被重置，1表示该区间被某种颜色覆盖。
35int n,q;
36char st[N];
37int cnt[27]; //计数排序.
38void PushUp(int rt,int id)
39{
40 tree[id][rt] = tree[id][rt<<1] + tree[id][rt<<1|1];
41}
42void PushDown(int l,int r,int rt,int id)
43{
44 if (lazy[id][rt]==-1) return ;
45 if (l==r) return;
46 lazy[id][rt<<1] = lazy[id][rt<<1|1] = lazy[id][rt]; //可以把一段区间被某种字母覆盖看做被染色。。。不过我们不需要知道被哪种字母染色，只需要知道是否被染色。
47 if (lazy[id][rt]) //如果一段区间被某种字母覆盖，那么该区间某种字母的数目就是区间长度，这也是PushDown需要传递区间端点l,r进来的原因。
48 {
49 int m = (l+r)>>1;
50 tree[id][rt<<1] = m-l+1;
51 tree[id][rt<<1|1] = r-m; //区间长度
52 }
53 else tree[id][rt<<1] = tree[id][rt<<1|1] = 0 ; //如果被重置了，清空线段树数组。
54 lazy[id][rt] = -1;
55 //关于lazy标记的思考：lazy标记是为了延迟更新。。。因此PushDown操作的内容其实和update时候的东西是非常相似的。。。
56}
57void build ( int l,int r,int rt)
58{
59 if (l==r)
60 {
61 int id = st[l]-'a'+1;
62 tree[id][rt] = 1;
63 lazy[id][rt] = 1;
64 return;
65 }
66 int m = (l+r)>>1;
67 build(lson);
68 build(rson);
69 for ( int i = 1 ; i <= 26 ; i++) //26棵线段树，每一层向上更新的时候每一棵都要记得更新。
70 PushUp(rt,i);
71}
72void update(int L,int R,int sc,int l,int r,int rt,int id)
73{
74 if (L<=l&&r<=R)
75 {
76 lazy[id][rt] = sc; //sc为0表示重置区间，sc为1表示该区间被id+'a'-1的字母覆盖。
77 if (sc) tree[id][rt] = r-l+1;
78 else tree[id][rt] = 0;
79 return;
80 }
81 PushDown(l,r,rt,id);
82 int m = (l+r)>>1;
83 if (L<=m) update(L,R,sc,lson,id);
84 if (R>=m+1) update(L,R,sc,rson,id);
85 PushUp(rt,id);
86}
87int query(int L,int R,int l,int r,int rt,int id)
88{
89 if (L<=l&&r<=R) return tree[id][rt];
90 PushDown(l,r,rt,id);
91 int m = (l+r)>>1;
92 int ret = 0 ;
93 if (L<=m) ret = ret + query(L,R,lson,id);
94 if (R>=m+1) ret = ret + query(L,R,rson,id);
95 PushUp(rt,id);
96 return ret;
97}
98int main()
99{
100#ifndef ONLINE_JUDGE
101 freopen("code/in.txt","r",stdin);
102#endif
103 ms(tree,0);
104 ms(lazy,-1);
105 cin>>n>>q;
106 scanf("%s",st+1);
107 build(1,n,1);
108 while (q--)
109 {
110 int l,r,k;
111 scanf("%d%d%d",&l,&r,&k);
112 for ( int i = 1 ; i <= 26 ; i++)
113 {
114 cnt[i] = query(l,r,1,n,1,i);
115 update(l,r,0,1,n,1,i); //初始要把[l,r]区间的每个字母的线段树区间重置，因为排序会打乱，在下面按照k的不同以不同方式（正序，逆序）更新。
116 }
117 if (k==1)
118 {
119 int pos = l;
120 for ( int i = 1 ; i <= 26 ; i++)
121 {
122 if (cnt[i]==0) continue;
123 update(pos,pos+cnt[i]-1,1,1,n,1,i);
124 pos = pos + cnt[i];
125 }
126 }
127 else
128 {
129 int pos = l;
130 for ( int i = 26 ; i >= 1 ; i--)
131 {
132 if (cnt[i]==0) continue;
133 update(pos,pos+cnt[i]-1,1,1,n,1,i);
134 pos = pos + cnt[i];
135 }
136 }
137 }
138 for ( int i = 1 ; i <= n ; i++)
139 {
140 for ( int j = 1 ; j <= 26 ; j++)
141 {
142 if (query(i,i,1,n,1,j)) //在第i个位置26个字母只可能有一种值为1，其余都为0，输出的时候query就好了。
143 {
144 printf("%c",j+'a'-1);
145 break;
146 }
147 }
148 }
149#ifndef ONLINE_JUDGE
150 fclose(stdin);
151#endif
152 return 0;
153}