题解 - C F 558 E A S i m p l e T a s k mathrm{CF558E A Simple Task} CF558E A Simple Task
吐槽一下：
- 这道题目足足做了我 3 3 3个小时，我 s t m stm stm真的要吐血了。
题目意思
就是给你一长为 n ( ≤ 1 0 5 ) n(leq 10^5) n(≤105)个小写字母序列，支持两种操作：
- ( l , r , 0 ) (l,r,0) (l,r,0)：将 [ l , r ] [l,r] [l,r]升序
- ( l , r , 1 ) (l,r,1) (l,r,1)：将 [ l , r ] [l,r] [l,r]倒序
求出 m ( ≤ 1 0 5 ) m(leq 10^5) m(≤105)次操作后的序列。
S o l mathrm{Sol} Sol
- 可以说是一道经典套路题吧
- 我们首先建 26 26 26棵线段树维护每一个字母，相当于对于升序我们只要对于这段区间里的字母按 a − z mathrm{a-z} a−z的顺序依次加入，不停更新加入左端点即可，右端点即为左端点加这个字母的数量。倒序也同理，只要 z − a mathrm{z-a} z−a的顺序即可。
- 然后就是线段树的基本操作了（嘻嘻嘻，我调了半年。
- 说句实话：对于大多数题目，套路就是硬道理。。。
C o d e mathrm{Code} Code
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#include <bits/stdc++.h> using namespace std; inline int read() { int sum=0,ff=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') ff=-1; ch=getchar(); } while(isdigit(ch)) sum=sum*10+(ch^48),ch=getchar(); return sum*ff; } const int N=1e5+5; int n,m,ans; char ch[100001],res[100001]; struct seg { int tr[31][400001],laz[31][400001]; inline void init() { for ( int i=1;i<=26;i++ ) memset(laz[i],-1,sizeof(laz[i])); } inline void build(int rt,int l,int r) { if(l==r) { tr[ch[l]-'a'+1][rt]=1; return; } int mid=(l+r)/2; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); for ( int i=1;i<=26;i++ ) tr[i][rt]=(tr[i][rt<<1]+tr[i][rt<<1|1]); } inline void push_down(int rt,int l,int r,int col) { if(laz[col][rt]!=-1) { tr[col][rt]=laz[col][rt]*(r-l+1); int mid=(l+r)/2; tr[col][rt<<1]=laz[col][rt]*(mid-l+1); tr[col][rt<<1|1]=laz[col][rt]*(r-mid); laz[col][rt<<1]=laz[col][rt]; laz[col][rt<<1|1]=laz[col][rt]; laz[col][rt]=-1; } } inline void update(int rt,int l,int r,int ll,int rr,int col,int v) { if(ll<=l&&r<=rr) { tr[col][rt]=v*(r-l+1); laz[col][rt]=v; return; } push_down(rt,l,r,col); int mid=(l+r)/2; if(ll<=mid) update(rt<<1,l,mid,ll,rr,col,v); if(rr>mid) update(rt<<1|1,mid+1,r,ll,rr,col,v); tr[col][rt]=tr[col][rt<<1]+tr[col][rt<<1|1]; } inline int query(int rt,int l,int r,int ll,int rr,int col) { if(ll<=l&&r<=rr) return tr[col][rt]; push_down(rt,l,r,col); int mid=(l+r)/2; int sum=0; if(ll<=mid) sum+=query(rt<<1,l,mid,ll,rr,col); if(rr>mid) sum+=query(rt<<1|1,mid+1,r,ll,rr,col); return sum; } inline void print(int rt,int l,int r) { if(l==r) { for ( int i=1;i<=26;i++ ) if(tr[i][rt]) { res[l]='a'+i-1; break; } return; } for ( int i=1;i<=26;i++ ) push_down(rt,l,r,i); int mid=(l+r)/2; print(rt<<1,l,mid); print(rt<<1|1,mid+1,r); } }; seg T; int main() { n=read(); m=read(); scanf("%s",ch+1); T.init(); T.build(1,1,n); for (;m--;) { int op,x,y; x=read(),y=read(),op=read(); if(op==1) { int tmp=x-1; for ( int j=1;j<=26;j++ ) { int cas=T.query(1,1,n,x,y,j); if(!cas)continue; T.update(1,1,n,x,y,j,0); T.update(1,1,n,tmp+1,tmp+cas,j,1); tmp=tmp+cas; } } else { int lp=x-1; for ( int j=26;j>=1;j-- ) { int sum=T.query(1,1,n,x,y,j); if(!sum) continue; T.update(1,1,n,x,y,j,0); T.update(1,1,n,lp+1,lp+sum,j,1); lp+=sum; } } } T.print(1,1,n); for ( int i=1;i<=n;i++ ) putchar(res[i]); return 0; } /* 10 5 abacdabcda 7 10 0 5 8 1 1 4 0 3 6 0 7 10 1 */
最后
以上就是着急铅笔最近收集整理的关于题解 - CF558E A Simple Task题解 - C F 558 E A S的全部内容，更多相关题解内容请搜索靠谱客的其他文章。
![[bzoj4552][二分][线段树]排序](/uploads/reation/bcimg1.png)
![[TJOI2016]排序——[线段树]](/uploads/reation/bcimg7.png)
发表评论 取消回复