非常好的一道题，是线段树的常见玩法
将字符串转化为1~26个数
对区间开一棵线段树，用两个数组分别维护区间中1~26每个数的个数以及一个区间覆盖标记，表示这个区间是否被某一个值覆盖了
在每次排序时，首先查出这个区间中1~26每个数出现的次数，然后因为是排过序的，所以相等的数排完序之后一定是连续的一段区间，这样如果升序，我们就对整个区间从小到大进行覆盖，否则从大到小覆盖
最后遍历整棵线段树输出即可
一句话总结：每次排序只需做一次区间查询，26次区间覆盖，这样时间复杂度O（26nlogn）
复制代码
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #define ls tree[rt].lson #define rs tree[rt].rson #define rt1 rt<<1 #define rt2 (rt<<1)|1 using namespace std; struct Tree { bool tag[30]; int s[30]; int lson; int rson; }tree[400005]; struct node { int v[30]; }zero; int n,q; int a[100005]; char s[100005]; void pushdown(int rt) { if(ls==rs) { return; } for(int i=1;i<=26;i++) { if(tree[rt].tag[i]) { for(int j=1;j<=26;j++) { tree[rt1].tag[j]=0; tree[rt1].s[j]=0; tree[rt2].tag[j]=0; tree[rt2].s[j]=0; } tree[rt1].tag[i]=1; tree[rt2].tag[i]=1; tree[rt1].s[i]=tree[rt1].rson-tree[rt1].lson+1; tree[rt2].s[i]=tree[rt2].rson-tree[rt2].lson+1; tree[rt].tag[i]=0; break; } } } void buildtree(int rt,int l,int r) { tree[rt].lson=l; tree[rt].rson=r; if(l==r) { tree[rt].s[a[l]]=1; return; } int mid=(l+r)>>1; buildtree(rt1,l,mid); buildtree(rt2,mid+1,r); for(int i=1;i<=26;i++) { tree[rt].s[i]=tree[rt1].s[i]+tree[rt2].s[i]; } } node add(node x,node y) { node ret=zero; for(int i=1;i<=26;i++) { ret.v[i]=x.v[i]+y.v[i]; } return ret; } node query(int rt,int l,int r) { if(ls>r||rs<l) { return zero; }else if(ls>=l&&rs<=r) { node ret=zero; for(int i=1;i<=26;i++) { ret.v[i]=tree[rt].s[i]; } return ret; } pushdown(rt); int mid=(ls+rs)>>1; return add(query(rt1,l,r),query(rt2,l,r)); } void update(int rt,int l,int r,int val) { if(ls>r||rs<l) { return; } if(ls>=l&&rs<=r) { for(int i=1;i<=26;i++) { tree[rt].s[i]=0; tree[rt].tag[i]=0; } tree[rt].tag[val]=1; tree[rt].s[val]=rs-ls+1; return; } pushdown(rt); int mid=(ls+rs)>>1; if(l<=mid) { update(rt1,l,r,val); } if(r>mid) { update(rt2,l,r,val); } for(int i=1;i<=26;i++) { tree[rt].s[i]=tree[rt1].s[i]+tree[rt2].s[i]; } } void pushit(int rt) { pushdown(rt); if(ls==rs) { return; } pushit(rt1); pushit(rt2); } void print(int rt) { if(ls==rs) { for(int i=1;i<=26;i++) { if(tree[rt].s[i]) { printf("%c",i-1+'a'); return; } } } print(rt1); print(rt2); } inline int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { // freopen("third.in","r",stdin); // freopen("third.out","w",stdout); n=read(),q=read(); scanf("%s",s+1); for(int i=1;i<=n;i++) { a[i]=s[i]-'a'+1; } buildtree(1,1,n); for(int i=1;i<=q;i++) { int l=read(),r=read(),typ=read(); node temp=query(1,l,r); if(typ==1) { for(int j=1;j<=26;j++) { update(1,l,l+temp.v[j]-1,j); l+=temp.v[j]; } }else { for(int j=26;j>=1;j--) { update(1,l,l+temp.v[j]-1,j); l+=temp.v[j]; } } } pushit(1); print(1); printf("n"); return 0; }
最后
以上就是缓慢小天鹅最近收集整理的关于CF558E的全部内容，更多相关CF558E内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复