Skip to content

Gym104008M - Youth Finale

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

Finales are born to be exciting. Performers play hard to draw audiences’ attention and then take a perfect curtain call. As the last problem and the finale of the problem set, however, we want you to recall a simple algorithm. Like me, it may be the first algorithm you’ve learned, called Bubble Sort.

1
2
3
4
5
6
7
8
9
void bubble_sort(int a[], int n) {  // 0-based, sort from lowest to highest
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
} // after i-th inner iteration, a[n - i] is correct
}
}

Given a permutation of length nn, as you might know, Bubble Sort runs in O(n2)O(n ^ 2) in the worst case. It’s quite a traditional idea to count the number of calls of 「swap」 in the algorithm. As you are stronger now, you want to count that number in a dynamic permutation with the following events that might happen:

  • Reverse the permutation, meaning that the permutation is replaced with

    p={pn,pn1,,p2,p1}p' = \{p_n, p_{n - 1}, \dots, p_2, p_1\}

  • Shift the permutation to the left by 11, meaning that the permutation is replaced with

    p={p2,p3,,pn,p1}p' = \{p_2, p_3, \dots, p_n, p_1\}

All you need to do is to output the number of 「swap」 that would be called if we sort the permutation with the above Bubble Sort code after each operation.

#输入格式

The first line contains two integers n,mn, m (1n3×1051 \leq n \leq 3 \times 10 ^ 5, 1m6×1051 \leq m \leq 6 \times 10 ^ 5), denoting the length of permutation and the number of operations.

The second line contains nn integers separated by spaces, and the ii-th denotes the initial pip_i.

The third line contains a single string containing $$mm$$ letters consisting of 『R』 and 『S』. The ii-th letter denotes the ii-th operation, where 『R』 or 『S』 denotes the Reverse or Shift operation, respectively.

It’s guaranteed that pp forms a correct permutation of 1,2,,n1, 2, \dots, n.

#输出格式

In the first line, print the number of 「swap」 would be called when Bubble Sort the initial pp.

In the second line, print a single string of mm digits. The ii-th denotes the number of 「swap」 would be called to Bubble Sort the permutation, modulo 1010.

#样例输入输出

样例输入 #1

5 10
5 4 3 2 1
SSSSRSSSSR

样例输出 #1

10
6446466400

#思路

给出一个长度为 nn 的排列 aamm 次操作,操作 SS 可以将 a1a_1 移到数组的最右侧,操作 RR 可以倒置数组,求初始数组和每次操作后逆序对的数量。

求初始数组的逆序对直接用树状数组完成即可。

进行 Shift 操作时,逆序对的数量要减去原来第一个数的逆序对的数量,除此之外还要减去移动后的正序对的数量。

进行 Reverse 操作时,逆序对的数量会变为原数组的正序对的数量。

使用 std::deque 维护序列即可。

#代码

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
#include <iostream>
#include <deque>
#include <string>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 3e5 + 5;

int n, m, p[N], c[N];
long long ans;
bool reversed;
std::string s;
std::deque<int> q;

int lowbit(int x) {
return x & -x;
}

void add(int x, int y) {
for (; x <= n; x += lowbit(x)) c[x] += y;
}

int sum(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += c[x];
return res;
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> m;

for (int i = 1; i <= n; i++) {
cin >> p[i];

q.emplace_back(p[i]);
}

for (int i = n; i; i--) {
ans += sum(p[i]);
add(p[i], 1);
}

cout << ans << endl;

cin >> s;

for (char c : s) {
if (c == 'S') {
int u;

if (reversed) {
u = q.back();
q.pop_back();
q.push_front(u);
} else {
u = q.front();
q.pop_front();
q.push_back(u);
}

ans += (n - 2 * u + 1);
} else { // c == 'R'
reversed = !reversed;
ans = static_cast<long long>(n) * (n - 1) / 2 - ans;
}

cout << ans % 10;
}

cout << endl;

return 0;
}