CodeForces#558 E.A Simple Task

发表于 | 分类于 | ℃热度
~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

E.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.

简要翻译

给定一个长度不超过$10^5$的字符串（小写英文字母），和不超过$5×10^4$个操作。

每个操作 $L\ R\ K$ 表示给区间$[L,R]$的字符串排序，$K=1$为升序，$K=0$为降序。

最后输出最终的字符串。

Input

第一行包含两个整数$n,q$，$n$代表字符串的长度，$q$代表询问的个数。

第二行包含一个字符串$S$。$S$只包含小写英文字母。

以下$q$行每行包含三个整数$i\ j\ k$。

Output

输出一行表示经过$q$次操作之后的字符串$S$。

Sample Input 1

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

Sample Output 1

cbcaaaabdd

Sample Input 2

10 1
agjucbvdfk
1 10 1

Sample Output 2

abcdfgjkuv

Hint

$1\le n\le 10^5$，$0\le q\le 50,000$。

$1\le i\le j\le n$，$k∈\{0,1\}$。

样例解释1

abacdabcda → abacdadcba

abacdadcba → abacacddba

abacacddba → cbaaacddba

cbaaacddba → cbcaaaddba

cbcaaaddba → cbcaaaabdd

我们用线段树来维护’$a$’-‘$c$’，我们可以用数字$1$~$26$代替。

我们每次改变序列时，先查询该区间内$1$~$26$每个数出现的次数，排完序后，我们可以知道该区间一定是连续的一段区间。

如果是升序，我们就对整个区间从小到大覆盖。

如果是降序，那就从大到小覆盖。

最后遍历一遍线段树输出即可。

总时间复杂度为$O(26nlogn)$

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
#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
const int N=100010;
struct seg_tree
{
	bool is_changed[28];
	int letter[28];
	int l,r;
}t[N<<2];
struct node
{
	int g[28];
};
void clear(node &g)
{
	for(int i=1;i<=26;++i) g.g[i]=0;
}
int n,q,a[N];
char c[N];
void pushup(int root)
{
	for(int i=1;i<=26;++i) t[root].letter[i]=t[root<<1].letter[i]+t[root<<1|1].letter[i];
}
void build(int root,int l,int r)
{
	t[root].l=l,t[root].r=r;
	if(l==r)
	{
		++t[root].letter[a[l]];
		return;
	}
	int mid=l+r>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	pushup(root);
}
void pushdown(int root,int l,int r)
{
	if(t[root].l==t[root].r) return;
	for(int i=1;i<=26;++i)
		if(t[root].is_changed[i])
		{
			for(int j=1;j<=26;++j)
			{
				t[root<<1].is_changed[j]=0;
				t[root<<1].letter[j]=0;
				t[root<<1|1].is_changed[j]=0;
				t[root<<1|1].letter[j]=0;
			}
			t[root<<1].is_changed[i]=1;
			t[root<<1].letter[i]=t[root<<1].r-t[root<<1].l+1;
			t[root<<1|1].is_changed[i]=1;
			t[root<<1|1].letter[i]=t[root<<1|1].r-t[root<<1|1].l+1;
			t[root].is_changed[i]=0;
		}
}
node add(node a,node b)
{
	node g; clear(g);
	for(int i=1;i<=26;++i) g.g[i]=a.g[i]+b.g[i];
	return g;
}
node query(int root,int l,int r,int ll,int rr)
{
	if(r<ll||l>rr) 
	{
		node g;
		clear(g);
		return g;
	}
	if(ll<=l&&r<=rr)
	{
		node g; clear(g);
		for(int i=1;i<=26;++i) g.g[i]=t[root].letter[i];
		return g;
	}
	pushdown(root,l,r);
	int mid=l+r>>1;
	node g; clear(g);
	if(ll<=mid) g=add(g,query(root<<1,l,mid,ll,rr));
	if(rr>mid) g=add(g,query(root<<1|1,mid+1,r,ll,rr));
	return g;
}
void change(int root,int l,int r,int ll,int rr,int k)
{
	if(r<ll||l>rr) return;
	if(ll<=l&&r<=rr)
	{
		for(int i=1;i<=26;++i) t[root].letter[i]=t[root].is_changed[i]=0;
		t[root].is_changed[k]=1;
		t[root].letter[k]=t[root].r-t[root].l+1;
		return;
	}
	pushdown(root,l,r);
	int mid=l+r>>1;
	if(ll<=mid) change(root<<1,l,mid,ll,rr,k);
	if(rr>mid) change(root<<1|1,mid+1,r,ll,rr,k);
	pushup(root);
}
void push_all_down(int root,int l,int r)
{
	pushdown(root,l,r);
	if(l==r) return;
	int mid=l+r>>1;
	push_all_down(root<<1,l,mid);
	push_all_down(root<<1|1,mid+1,r);
}
void print(int root,int l,int r)
{
	if(l==r)
	{
		for(int i=1;i<=26;++i)
			if(t[root].letter[i])
			{
				putchar((char)((int)'a'+i-1));
				return;
			}
	}
	int mid=l+r>>1;
	print(root<<1,l,mid);
	print(root<<1|1,mid+1,r);
}
int main(int argc, char const *argv[])
{
	n=read(),q=read();
	scanf("%s",c+1);
	for(int i=1;i<=n;++i) a[i]=c[i]-'a'+1;
	build(1,1,n);
	while(q--)
	{
		int l=read(),r=read(),k=read();
		node g=query(1,1,n,l,r);
		for(int i=(k==1? 1:26);(k==1? i<=26:i>=1);l+=g.g[(k==1? i++:i--)])
			change(1,1,n,l,l+g.g[i]-1,i);
	}
	push_all_down(1,1,n);
	print(1,1,n);
	return 0;
}
-------------本文结束(づ￣ 3￣)づ~感谢您的阅读(*╹▽╹*)-------------