练琴记录：解法与部分分

先把“一轮弹很多遍”拆开．设本轮前缀为 $P=a_1,\ldots,a_x$，重复 $c$ 遍．记：

• $I_x$：一份 $P$ 内部的逆序对数．
• $D_x$：两份 $P$ 按先后拼接时，前一份到后一份的逆序对数．
• $H_x$：已有全部历史记录到一份 $P$ 的逆序对数．

新增逆序对分为历史到本轮、同一遍内部、本轮不同遍之间，分别贡献

$D_x$ 等于前缀里不同位置且值不同的无序对数量：两份前缀里，一大一小的两个值必有一个方向满足大于．相等的不计．$I,D$ 都能用按值计数的树状数组预处理．

剩下的难点只有：前缀会变，历史还在，怎样维护 $H_x$？

先固定历史，移动前缀端点

设历史中各音高出现次数已经可以查询．前缀新增一个音符 $a_j$ 时，$H$ 增加“历史中严格大于 $a_j$ 的音符数”；前缀删去末尾音符时，减去同一个数．这里删的是本轮准备练的前缀，不是历史记录．

由于每一轮前缀最多增长一位，全部向右移动不超过 $n$ 次；向左移动总数不超过向右移动总数．所以可以逐位处理端点移动，而不必寻找一次删除整段的复杂结构．

再固定前缀，追加整轮练习

把曲谱位置 $j$ 在历史中出现的次数写成

$z$ 是当前练习前缀共同携带的增量，$b_j$ 是各位置的补偿值．树状数组按音高维护两种和：补偿值之和、当前前缀内的位置数．因此历史里大于 $v$ 的总次数为

前缀扩展到位置 $j$ 时，让 $b_j\gets b_j-z$，再把它加入活动前缀；缩短移出它时，让 $b_j\gets b_j+z$，再移出活动前缀．两种补偿都保证真实历史次数 $h_j$ 没变．这也解释了为什么退出后重新进入的音符不会丢掉旧记录．

现在追加 $c$ 遍，只需要让 $z\gets z+c$．历史到当前前缀的逆序对数同时增加 $cD_x$，所以更新 $H\gets H+cD_x$．

处理顺序为：先移动端点并修正 $H$，再用旧的 $H$ 计算本轮新增答案，最后更新 $z,H$．

预处理与每次单点维护均为 $O(\log n)$，端点总移动 $O(n)$，总时间 $O(n\log n)$，空间 $O(n)$．次数、组合数和树状数组都可以按模数维护，因为只用于加乘，不用它们比较大小；比较的是原音高．

部分分

其中 $L$ 只用于描述展开长度，完整解法不需要实际计算或分配 $L$ 个位置．

参考程序

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;

ll norm(ll x) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

struct BIT {
    int n;
    vector<ll> t;
    explicit BIT(int n) : n(n), t(n + 1) {}
    void add(int x, ll v) {
        v = norm(v);
        for (; x <= n; x += x & -x) t[x] = (t[x] + v) % mod;
    }
    ll sum(int x) const {
        ll res = 0;
        for (; x; x -= x & -x) res = (res + t[x]) % mod;
        return res;
    }
    ll greater(int x) const {
        return norm(sum(n) - sum(x));
    }
};

ll solve(const vector<int>& a, const vector<pair<int, ll>>& ops) {
    int n = (int)a.size() - 1;
    vector<int> val(a.begin() + 1, a.end()), rank(n + 1);
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    int m = (int)val.size();
    for (int i = 1; i <= n; i++)
        rank[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;

    vector<ll> inside(n + 1), unequal(n + 1);
    vector<int> freq(m + 1);
    BIT prep(m);
    for (int i = 1; i <= n; i++) {
        inside[i] = (inside[i - 1] + prep.greater(rank[i])) % mod;
        unequal[i] = (unequal[i - 1] + i - 1 - freq[rank[i]]) % mod;
        freq[rank[i]]++;
        prep.add(rank[i], 1);
    }

    BIT base(m), active(m);
    ll z = 0, h = 0, ans = 0;
    int cur = 0;
    auto greater = [&](int v) {
        return (base.greater(v) + z * active.greater(v)) % mod;
    };
    for (auto op : ops) {
        int x = op.first;
        ll c = op.second % mod;
        while (cur < x) {
            ++cur;
            int v = rank[cur];
            h = (h + greater(v)) % mod;
            base.add(v, -z);
            active.add(v, 1);
        }
        while (cur > x) {
            int v = rank[cur];
            h = norm(h - greater(v));
            base.add(v, z);
            active.add(v, -1);
            --cur;
        }
        ll choose = c * norm(c - 1) % mod * inv2 % mod;
        ans = (ans + c * h + c * inside[x]) % mod;
        ans = (ans + choose * unequal[x]) % mod;
        z = (z + c) % mod;
        h = (h + c * unequal[x]) % mod;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef SELF_TEST_BATCH
    int cases;
    cin >> cases;
    while (cases--) {
#endif
        int n;
        if (!(cin >> n)) return 0;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];
        vector<pair<int, ll>> ops(n);
        for (auto& op : ops) cin >> op.first >> op.second;
        cout << solve(a, ops) << '\n';
#ifdef SELF_TEST_BATCH
    }
#endif
}