```cpp
#include<bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void write(T res)
{
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
const int N = 2e4 + 5, M = 2e6;
int n, m;
int a[N];
namespace pol{
struct Node{
int v, s[2], pri, cnt;
}tr[M];
int dust_bin[M], num;
int tot, root[N << 4], x, y, z;
inline int make(int x)
{
if(!num) return tr[++ tot].v = x, tr[tot].pri = rand(), tr[tot].cnt = 1, tot;
return tr[dust_bin[num]].v = x, tr[dust_bin[num]].pri = rand(), tr[dust_bin[num]].cnt = 1, num --, dust_bin[num + 1];
}
inline void pushup(int x)
{
tr[x].cnt = tr[tr[x].s[0]].cnt + tr[tr[x].s[1]].cnt + 1;
}
inline int merge(int x, int y)
{
if(!x || !y) return x + y;
if(tr[x].pri <= tr[y].pri)
{
tr[x].s[1] = merge(tr[x].s[1], y);
pushup(x);
return x;
}
else {
tr[y].s[0] = merge(x, tr[y].s[0]);
pushup(y);
return y;
}
}
inline void split(int now, int k, int &x, int &y)
{
if(!now) x = y = 0;
else {
if(tr[now].v <= k) x = now, split(tr[now].s[1], k, tr[now].s[1], y);
else y = now, split(tr[now].s[0], k, x, tr[now].s[0]);
pushup(now);
}
}
inline void remove(int id, int v)
{
split(root[id], v, x, z);
split(x, v - 1, x, y);
if(y != 0) dust_bin[++ num] = y;
y = merge(tr[y].s[0], tr[y].s[1]);
root[id] = merge(x, merge(y, z));
}
inline void insert(int id, int v)
{
split(root[id], v, x, y);
root[id] = merge(x, merge(make(v), y));
}
inline int get_front(int id, int v)
{
split(root[id], v - 1, x, y);
z = tr[x].cnt;
root[id] = merge(x, y);
return z;
}
inline int get_back(int id, int v)
{
split(root[id], v, x, y);
z = tr[y].cnt;
root[id] = merge(x, y);
return z;
}
}
struct Node{
int l, r;
}tr[N << 4];
inline void build(int x, int l, int r)
{
tr[x] = {l, r};
for(int i = l;i <= r;i ++)
pol:: insert(x, a[i]);
if(l == r) return ;
int mid = l + r >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
}
inline int query_max(int x, int l, int r, int v)
{
if(l <= tr[x].l && tr[x].r <= r) return pol:: get_back(x, v);
int mid = tr[x].l + tr[x].r >> 1, res = 0;
if(l <= mid) res += query_max(x << 1, l, r, v);
if(r > mid) res += query_max(x << 1 | 1, l, r, v);
return res;
}
inline int query_min(int x, int l, int r, int v)
{
if(l <= tr[x].l && tr[x].r <= r) return pol:: get_front(x, v);
int mid = tr[x].l + tr[x].r >> 1, res = 0;
if(l <= mid) res += query_min(x << 1, l, r, v);
if(r > mid) res += query_min(x << 1 | 1, l, r, v);
return res;
}
inline void modify_del(int x, int l, int v)
{
pol:: remove(x, v);
if(tr[x].l == tr[x].r) return ;
int mid = tr[x].l + tr[x].r >> 1;
if(l <= mid) modify_del(x << 1, l, v);
else modify_del(x << 1 | 1, l, v);
}
inline void modify_add(int x, int l, int v)
{
pol:: insert(x, v);
if(tr[x].l == tr[x].r) return ;
int mid = tr[x].l + tr[x].r >> 1;
if(l <= mid) modify_add(x << 1, l, v);
else modify_add(x << 1 | 1, l, v);
}
int ans, o, u;
int main()
{
read(n);
for(int i = 1;i <= n;i ++) read(a[i]);
read(m);
build(1, 1, n);
for(int i = 1;i < n;i ++)
ans += query_min(1, i + 1, n, a[i]);
write(ans), puts("");
while(m --)
{
read(o, u);
if(o > u) swap(o, u);
if(o != u) ans -= query_max(1, o + 1, u, a[u]);
if(o != u) ans -= query_min(1, o, u - 1, a[o]);
if(a[u] < a[o]) ans --;
modify_del(1, o, a[o]), modify_del(1, u, a[u]);
swap(a[o], a[u]);
modify_add(1, o, a[o]), modify_add(1, u, a[u]);
if(o != u) ans += query_max(1, o + 1, u, a[u]);
if(o != u) ans += query_min(1, o, u - 1, a[o]);
if(a[u] < a[o]) ans ++;
write(ans), puts("");
}
return 0;
}
```
by lucky叶 @ 2022-04-21 19:46:53
破案了，垃圾桶中点的儿子没清空
by lucky叶 @ 2022-04-21 22:03:54