官方题解(见M题)

一种参考代码：(如果你不会树状数组，把下面树状数组部分用归并排序代替即可，其中 deque 是双端队列，能 O(1) 实现增删和访问首尾)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mn = 3e5 + 10;
ll n, m, t[mn], rev, s;
char c[mn * 2]; //怎么这里*2还能WA你一下
deque<ll> p;
#define lowbit(x) (x & (-x))
void add(ll x, ll v)
{
    for (; x <= n; x += lowbit(x))
    {
        t[x] += v;
    }
}
ll query(ll rf)
{
    ll ans = 0;
    for (; rf > 0; rf -= lowbit(rf))
    {
        ans += t[rf];
    }
    return ans;
}
ll query(ll lf, ll rf) { return query(rf) - query(lf - 1); }
signed main()
{
    cin.tie(0)->ios::sync_with_stdio(false);
    cin >> n >> m;
    for (ll i = 1, v; i <= n; ++i)
    {
        cin >> v;
        s += query(v + 1, n);
        add(v, 1);
        p.push_front(v);
    }
    cout << s << '\n'; //不输出这个WA了一次
    cin >> c + 1;
    for (ll i = 1; i <= m; ++i)
    {
        if (c[i] == 'S')
        {
            if (!rev)
            {
                ll v = p.back();
                s -= v - 1; // query(1, v - 1);
                s += n - v; // query(v + 1, n);
                p.pop_back();
                p.push_front(v);
            }
            else
            {
                ll v = p.front();
                s -= n - v; // query(v + 1, n);
                s += v - 1; // query(1, v - 1);
                p.pop_front();
                p.push_back(v);
            }
        }
        else
        {
            rev ^= 1;
        }
        if (!rev)
        {
            cout << (s % 10);
        }
        else
        {
            cout << ((n * (n - 1) / 2 - s) % 10);
        }
    }
    return 0;
}