坐地铁的时候消磨时光看了一下速杀了 ABCDG

A

按题意模拟

B

数组长度 - 值域数组最大值

C

设势能函数为数组的和，每个操作一只会增加 1 势能，可知势能不会超过 Q，因此操作二的次数也是有上限的
维护非 0 的位置，每次操作二暴力减即可，时间复杂度 O(Q)O(Q)
可能需要使用 std::set 或者正确哈希函数的 std::unordered_set

D

设 Q 为对 P 进行操作二之后的序列，题目给了 Q[P[i]] = i，观察一下能发现 P[Q[i]] = i
因此维护 P 和 Q，操作一正常 swap(Q[P[x]], Q[P[y]]), swap(P[x], P[y])，操作二 swap(P, Q) 即可

E

呃呃，概率 dp，不想做

#include <bits/stdc++.h>
using i64 = long long;
using flt = long double;

flt dp[410][205][205];

auto solve() {
    int N, L;
    std::cin >> N >> L;

    i64 sum = 0;
    for (int _ = 0, v; _ < N; ++_)
        sum += (std::cin >> v, v);
    
    int M = 2 * N;
    for (int h = 0; h <= M; ++h) {
        for (int s = 0; s <= N; ++s) {
            for (int l = 0; l <= L; ++l) {
                if (l == 0 || s > h || h + s > M || ((h - s) & 1)) {
                    dp[h][s][l] = 0;
                    continue;
                }

                if (h == 0) { dp[h][s][l] = 0; continue; }

                flt res = 0;

                if (s > 0) res += (flt)s / h * (1 + dp[h - 1][s - 1][l]);
                if (h - s >= 2) {
                    flt nxt = 0;
                    nxt += (flt)1 / (h - 1) * (1 + dp[h - 2][s][l]);
                    if (s > 0) nxt += (flt)s / (h - 1) * ((l >= 2 ? (flt)1 : (flt)0) + dp[h - 2][s][l - 1]);
                    if (h - s >= 4) nxt += (flt)(h - s - 2) / (h - 1) * dp[h - 2][s + 2][l - 1];
                    res += (flt)(h - s) / h * nxt;
                }

                dp[h][s][l] = res;
            }
        }
    }

    std::cout << std::fixed << std::setprecision(40);
    std::cout << dp[2 * N][0][L] * sum / N << "\n";
}

F

好像是组合数学，不想想

G

先看固定一个点怎么求，找到一个点右侧的第一个 0 的位置，则 0 右侧的位置都贡献 1
找到右侧第一个 1 的位置，则 1 和 0 更靠右那一个右侧的位置都继续贡献 1
直到遍历值域 N

固定一个点，我们维护一个数组，B[值] = 右侧第一个位置，显然答案与 B 的前缀最大值的和有关
而从 1 开始往右遍历的过程中，只需要修改 B 数组中的一个值，如果我们有平衡单点修改和快速求和的数据结构，就能轻松解决这个问题

求出 B 的前缀最大值数组 C，每一次修改 B 的一个值，相当于修改了它的在 C 数组中的所有后缀，所以我们需要一个区间 max 和区间求和的数据结构
显然，可以尝试使用线段树维护以上信息

#include <bits/stdc++.h>

using i64 = long long;

struct SGT {
    static constexpr i64 INF = (1ull << 60);
    struct Info {
        i64 mn, mn2, cntmn;
        i64 sum;
    };
    const int n, beg, end, rt;
    std::vector<Info> sgt;

    SGT(const std::vector<i64>& a)
    :n(a.size()), beg(0), end(n), rt(1) {
        sgt.resize((n + 1) << 2);
        build(beg, end, rt, a);
    }

    #define lson (p << 1)
    #define rson (p << 1 | 1)

    void apply(int p, i64 v) {
        sgt[p].sum += (v - sgt[p].mn) * sgt[p].cntmn;
        sgt[p].mn = v;
    }

    void push_up(int p) {
        const auto& a = sgt[lson];
        const auto& b = sgt[rson];
        sgt[p].mn = std::min(a.mn, b.mn);
        sgt[p].cntmn = (sgt[p].mn == a.mn ? a.cntmn : 0) + (sgt[p].mn == b.mn ? b.cntmn : 0);
        sgt[p].sum = a.sum + b.sum;
        sgt[p].mn2 = std::min(sgt[p].mn == a.mn ? a.mn2 : a.mn, sgt[p].mn == b.mn ? b.mn2 : b.mn);
    }

    void push_dw(int p) {
        if (sgt[p].mn > sgt[lson].mn) apply(lson, sgt[p].mn);
        if (sgt[p].mn > sgt[rson].mn) apply(rson, sgt[p].mn);
    }

    void build(int l, int r, int p, const std::vector<i64>& a) {
        if (l == r - 1) return sgt[p] = { a[l], INF, 1, a[l] }, void();
        int mid = (l + r) >> 1;
        build(l, mid, lson, a), build(mid, r, rson, a);
        push_up(p);
    }

    void chg_max(int x, int y, i64 v, int l, int r, int p) {
        if (r <= x || l >= y || v <= sgt[p].mn) return ;
        if (x <= l && r <= y && (l == r - 1 || v < sgt[p].mn2)) return apply(p, v);
        int mid = (l + r) >> 1;
        push_dw(p);
        chg_max(x, y, v, l, mid, lson), chg_max(x, y, v, mid, r, rson);
        push_up(p);
    }
    void chg_max(int x, int y, i64 v) { chg_max(x, y, v, beg, end, rt); }

    i64 que(int x, int y, int l, int r, int p) {
        if (x <= l && r <= y) return sgt[p].sum;
        int mid = (l + r) >> 1;
        push_dw(p);
        if (y <= mid) return que(x, y, l, mid, lson);
        if (x >= mid) return que(x, y, mid, r, rson);
        return que(x, y, l, mid, lson) + que(x, y, mid, r, rson);
    }
    i64 que(int x, int y) { return que(x, y, beg, end, rt); }

    #undef lson
    #undef rson
};

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

    int n;
    std::cin >> n;

    std::vector<i64> a(n);
    std::vector<int> nex(n);
    std::vector<i64> b(n + 1, n);

    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    for (int i = n - 1; i >= 0; --i)
        nex[i] = b[a[i]], b[a[i]] = i;
    for (int i = 0; i < n; ++i)
        if (i) b[i] = std::max(b[i - 1], b[i]);
    
    SGT sgt(b);
    i64 ans = 0;
    
    for (int i = 0; i < n; ++i) {
        ans += (i64)n * n - sgt.que(0, n);
        sgt.chg_max(a[i], n + 1, nex[i]);
    }

    std::cout << ans << "\n";
}