暴力做法：直接瞎写个东西暴力跑一下，找规律容易得到答案式子。（
操作很难刻画，考虑设一个势能函数来刻画这个东西。
设 \(\Phi(x) = \sum_{i=1}^n\sum_{j=i+1}^n |x_i - x_j|\)。容易发现，当我们将两个数进行操作时，\(\Phi(x)\) 的值至少会减少 \(2x\)。而交换两个相邻的数时，减少恰好 \(2x\)。那么显然 \(x\) 的和就是 \(\frac{\Phi(x)}{2}\) 了。
那么就直接拿数据结构维护一下即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 800005, P = 998244353, V = 1000000000;
struct SegmentTree {
struct Node {
int sum, tot, siz, lc, rc;
} t[MAXN * 33];
#define lc t[p].lc
#define rc t[p].rc
int tot;
void pushUp(int p) {
t[p].sum = (t[lc].sum - 1ll * t[lc].tot * t[rc].siz % P +
t[rc].sum + 1ll * t[rc].tot * t[lc].siz + P) % P;
t[p].tot = (t[lc].tot + t[rc].tot) % P;
t[p].siz = t[lc].siz + t[rc].siz;
}
void add(int d, int v, int &p, int l = 1, int r = V) {
if (!p) p = ++tot;
if (l == r) {
t[p].tot = (1ll * t[p].tot + l * v % P + P) % P;
t[p].siz += v;
return;
}
int mid = (l + r) >> 1;
if (d <= mid) add(d, v, lc, l, mid);
else add(d, v, rc, mid + 1, r);
pushUp(p);
}
} st;
int n, q, a[MAXN];
int main() {
int root = 0;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
st.add(a[i], 1, root);
}
for (int i = 1; i <= q; i++) {
int x, y; scanf("%d%d", &x, &y);
st.add(a[x], -1, root);
a[x] = y;
st.add(a[x], 1, root);
printf("%lld\n", 1ll * st.t[root].sum * (P + 1) / 2 % P);
}
return 0;
}