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
题意很简单，就是给你个字符串，然后又q次操作，每次操作有i,j,k三个值，如果k为0，就把i,j区间的字符降序排序，如果k = 1,就将i，j区间的字符串升序排序，最后输出这个字符串。下标从1开始。
直接暴力显然会超时，这个题因为只有26个小写字母，所以我们可以利用区间查询出这个区间每个字符的个数，先把这个区间所有字符的个数都更新为0，即相当于删去所有字符。然后再按照升或降的顺序从开头存放，即从新填放，这里面对于区间的操作我们就用到了线段树。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<bits/stdc++.h>
using namespace std;
#define lson (k*2)
#define rson (k*2+1)
const int MAX = 100010;
const int MAX_V = 28;
class Node{
public:
int l,r,v[MAX_V];
Node();
int mid(){
return (l+r)/2;
}
int len(){
return r-l+1;
}
};
int Lazy[MAX*4][MAX_V];
int N,Q;
char str[MAX];
Node tree[MAX*4];
void PushUp(int k,int id){
tree[k].v[id] = tree[lson].v[id] + tree[rson].v[id];
}
void PushDown(int k,int id){
if(Lazy[k][id] != -1){
int value = Lazy[k][id];
tree[lson].v[id] = tree[lson].len()*value;
tree[rson].v[id] = tree[rson].len()*value;
Lazy[lson][id] = value;
Lazy[rson][id] = value;
}
Lazy[k][id] = -1;
}
void Build(int L,int R,int k){
tree[k].l = L;
tree[k].r = R;
if(L == R){
int id = str[L]-'a';
tree[k].v[id] = 1;
return;
}
int mid = (L+R)/2;
Build(L,mid,lson);
Build(mid+1,R,rson);
for(int i=0;i<26;++i)
PushUp(k,i);
}
void Update(int L,int R,int add,int k,int id){
if(L <= tree[k].l && tree[k].r <= R){
tree[k].v[id] = add*tree[k].len();
Lazy[k][id] = add;
return;
}
PushDown(k,id);
int mid = tree[k].mid();
if(L <= mid)
Update(L,R,add,lson,id);
if(R > mid) Update(L,R,add,rson,id);
PushUp(k,id);
}
int Query(int L,int R,int k,int id){
if(L <= tree[k].l && tree[k].r <= R)
return tree[k].v[id];
PushDown(k,id);
int res = 0;
int mid = tree[k].mid();
if(L <= mid)
res += Query(L,R,lson,id);
if(R > mid)
res += Query(L,R,rson,id);
return res;
}
void Display(){
for(int i=1;i<=N;++i){
for(int id=0;id<26;++id){
if(Query(i,i,1,id)){
printf("%c",'a'+id);
}
}
}
printf("n");
}
void Show(int *bas){
for(int id=0;id<26;++id){
printf("%d ",bas[id]);
}
printf("n");
}
int main(void){
//这里要把lzay设置为-1，因为更新值可能为0，注意。
memset(Lazy,-1,sizeof(Lazy));
scanf("%d%d",&N,&Q);
scanf("%s",str+1);
Build(1,N,1);
int u,v,w;
int bas[MAX_V];//存储每个字符的个数
for(int i=1;i<=Q;++i){
scanf("%d%d%d",&u,&v,&w);
if(w == 0){
//查询该区间每个字符的个数。
for(int id=0;id<26;++id){
bas[id] = Query(u,v,1,id);
Update(u,v,0,1,id);
}
int l=u,r;
//0表示降序，即从后往前更新对应区间的字符。
for(int id=25;id>=0;--id){
if(bas[id]){
r = l+bas[id]-1;
Update(l,r,1,1,id);
l += bas[id];
}
}
}
else{
for(int id=0;id<26;++id){
bas[id] = Query(u,v,1,id);
Update(u,v,0,1,id);
}
int l=u,r;
for(int id=0;id<26;++id){
if(bas[id]){
r = l + bas[id]-1;
Update(l,r,1,1,id);
l += bas[id];
}
}
}
}
Display();
return 0;
}
Node::Node(){
l = r = 0;
memset(v,0,sizeof(v));
}
最后
以上就是留胡子黄豆最近收集整理的关于CodeForces - 558E A Simple Task （计数排序 线段树）的全部内容，更多相关CodeForces内容请搜索靠谱客的其他文章。
![[TJOI2016]排序——[线段树]](/uploads/reation/bcimg7.png)
发表评论 取消回复