Gym104008M - Youth Finale

#题面

#题目描述

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 $n$, as you might know, Bubble Sort runs in $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' = \{p_n, p_{n - 1}, \dots, p_2, p_1\}$$

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

  $$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, m$ ($1 \leq n \leq 3 \times 10 ^ 5$, $1 \leq m \leq 6 \times 10 ^ 5$), denoting the length of permutation and the number of operations.

The second line contains $n$ integers separated by spaces, and the $i$-th denotes the initial $p_i$.

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

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

#输出格式

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

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

#样例输入输出

样例输入 #1

5 10
5 4 3 2 1
SSSSRSSSSR

样例输出 #1

10
6446466400

#思路

给出一个长度为 $n$ 的排列 $a$ 和 $m$ 次操作，操作 $S$ 可以将 $a_1$ 移到数组的最右侧，操作 $R$ 可以倒置数组，求初始数组和每次操作后逆序对的数量。

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

进行 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;
}