【-31】558E. A Simple Task[线段树]

题目描述

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.

输入输出格式

输入格式

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$, img).

输出格式

Output one line, the string $S$ after applying the queries.

输入输出样例

输入样例1

1
2
3
4
5
6
7
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1

输出样例1

1
cbcaaaabdd

输入样例2

1
2
3
10 1
agjucbvdfk
1 10 1

输出样例2

1
abcdfgjkuv

说明

First sample test explanation:

img

img

img

img

img

题解

建26个线段树(每个字母对应一个),然后每次修改的时候就一棵棵的修改

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()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=(k<<3)+(k<<1)+(s-'0');
s=getchar();
}
return k*base;
}
const int maxn=1e5+1;
int t[26][300003];
int f[26][300003];
int l[300003];
int r[300003];
int n,m,X,Y,Z;
char ch[100003];
int sum[26];//存字母个数和
int ss;
inline void bt(int x,int y,int d)
{
l[d]=x;r[d]=y;
if (x==y)
{
t[ch[x]-'a'][d]++;
return;
}
int mid=(x+y)>>1;
bt(x,mid,d<<1);
bt(mid+1,y,d<<1|1);
int xx=d<<1;
for (int i=0;i<26;i++) t[i][d]=t[i][xx]+t[i][xx|1];//每个都要更新
}
//-------------------------------------------------------------
inline void down(int d,int D)
{
if (f[D][d]!=-1)//没有标记就不传
{
int xx=d<<1;
f[D][xx]=f[D][d];
f[D][xx|1]=f[D][d];

t[D][xx]=f[D][d]*(r[xx]-l[xx]+1);
t[D][xx|1]=f[D][d]*(r[xx|1]-l[xx|1]+1);

f[D][d]=-1;
}
}//往下传
inline void qh(int x,int y,int d,int D)//求x->y中D的出现次数
{
if (x<=l[d]&&r[d]<=y)
{
sum[D]+=t[D][d];
return;
}
if (t[D][d]==r[d]-l[d]+1)//如果下面全是这个字母就不要往下扫了
{
sum[D]+=y-x+1;
return;
}
if (t[D][d]==0) return;
down(d,D);
int mid=(l[d]+r[d])>>1;
if (y<=mid) qh(x,y,d<<1,D); else
if (x>mid) qh(x,y,d<<1|1,D); else
{
qh(x,mid,d<<1,D);
qh(mid+1,y,d<<1|1,D);
}
}
inline void xg(int x,int y,int d,int D,int flag)//把x->y这一段改成字母D flag=1:改为D,flag=0:改为0
{
if (x<=l[d]&&r[d]<=y)
{
t[D][d]=(r[d]-l[d]+1)*flag;
f[D][d]=flag;//标记
return;
}
down(d,D);//往下传
int mid=(l[d]+r[d])>>1;
if (y<=mid) xg(x,y,d<<1,D,flag); else
if (x>mid) xg(x,y,d<<1|1,D,flag); else
{
xg(x,mid,d<<1,D,flag);
xg(mid+1,y,d<<1|1,D,flag);
}
t[D][d]=t[D][d<<1]+t[D][d<<1|1];
}
inline void sc()//输出
{
for (register int i=1;i<=n;i++)
{
int j=0;
memset(sum,0,sizeof(sum));
for (;j<=25;j++)
{
qh(i,i,1,j);
if (sum[j]!=0) break;
}//一个一个的找
printf("%c",char(j+(int)'a'));
}
}
int main()
{
// freopen("string.in","r",stdin);
// freopen("string.out","w",stdout);
n=read();m=read();
scanf("%s",ch+1);
bt(1,n,1);
memset(f,-1,sizeof(f));
for (int II=1;II<=m;++II)
{
X=read();Y=read();Z=read();
memset(sum,0,sizeof(sum));
for (int i=0;i<=25;++i)
{
qh(X,Y,1,i);
}
int now=X;
if (Z==0)//降序
{
for (int i=25;i>=0;--i)
{
if (sum[i]==0) continue;
xg(now,now+sum[i]-1,1,i,1);//这一段全部改为这个字母
if (X<=now-1) xg(X,now-1,1,i,0);//其他部分全部清空
if (now+sum[i]<=Y) xg(now+sum[i],Y,1,i,0);
now=now+sum[i];
}
}
else//升序
{
for (int i=0;i<26;++i)
{
if (sum[i]==0) continue;
xg(now,now+sum[i]-1,1,i,1);
if (X<=now-1) xg(X,now-1,1,i,0);
if (now+sum[i]<=Y) xg(now+sum[i],Y,1,i,0);
now=now+sum[i];
}
}
}
sc();
return 0;
}