萌新求助，关于树套树空间

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;
namespace FastIO {
    template<typename T> inline void in(T &s){
        int f=1; char c=getchar(); s=0;
        while(!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
        while(isdigit(c)) s=(s<<3)+(s<<1)+(c^48), c=getchar();
        s*=f;
    }
    template<typename T> inline void out(T s){
        if(s<0) putchar('-'), s=-s;
        if(s>9) out(s/10);
        putchar('0'+s%10);
    }
    template<typename T> inline void outc(T s, char c='\n') { out(s), putchar(c); };
} using namespace FastIO;

typedef unsigned long long uLL;
typedef long long LL;
const int INF=0x3f3f3f3f;

const int _=5, N=2e4, M=2e3, V=1e9, LgN=15;

int n, m, on, res, cnt, o[N+_], h[N+_], a[N+_];

struct fhq_node {
    int v, sz, ls, rs, ky;
    fhq_node () { v=sz=ls=rs=ky=0; }
    fhq_node (int _v) { v=_v, sz=1, ky=rand(), ls=rs=0; }
} t[N*LgN*2+_]; // 这里 qwq

struct fhq_tree {
    int rot;
    fhq_tree () { rot=0; }
    inline int nw(int v) { return t[++cnt]=fhq_node(v), cnt; }
    inline void pushup(int rt) { t[rt].sz=t[t[rt].ls].sz+t[t[rt].rs].sz+1; }
    inline void split(int rt, int vl, int &x, int &y){
        if(!rt) { x=y=0; return ; }
        if(t[rt].v<=vl) x=rt, split(t[rt].rs, vl, t[rt].rs, y);
        else y=rt, split(t[rt].ls, vl, x, t[rt].ls);
        pushup(rt);
    }
    inline int merge(int x, int y){
        if(!x||!y) return x|y;
        if(t[x].ky<t[y].ky){
            t[x].rs=merge(t[x].rs, y);
            pushup(x); return x;
        }else{
            t[y].ls=merge(x, t[y].ls);
            pushup(y); return y;
        }
    }
    inline void insert(int v){
        int x, y;
        split(rot, v, x, y);
        rot=merge(x, merge(nw(v), y));
    }
    inline void erase(int v){
        int x, y, z;
        split(rot, v-1, x, y);
        split(y, v, y, z);
        y=merge(t[y].ls, t[y].rs);
        rot=merge(x, merge(y, z));
    }
    inline int more(int v){
        int x, y, ans;
        split(rot, v, x, y);
        ans=t[y].sz;
        rot=merge(x, y);
        return ans;
    }
    inline int less(int v){
        int x, y, ans;
        split(rot, v-1, x, y);
        ans=t[x].sz;
        rot=merge(x, y);
        return ans;
    }
} bt[(N<<2)+_];

inline int lowbit(int x) { return x&(-x); }
inline void add(int p, int x) { while(p<=n) a[p]+=x, p+=lowbit(p); }
inline int sum(int p) { int s=0; while(p) s+=a[p], p-=lowbit(p); return s; }

inline void build(int rt, int l, int r){
    for(int i=l; i<=r; ++i) bt[rt].insert(h[i]);
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(rt<<1, l, mid), build(rt<<1|1, mid+1, r);
}
inline int mor(int rt, int l, int r, int u, int w){
    if(1<=l&&r<=u) return bt[rt].more(w);
    int ans=0, mid=(l+r)>>1;
    if(1<=mid) ans+=mor(rt<<1, l, mid, u, w);
    if(u>mid) ans+=mor(rt<<1|1, mid+1, r, u, w);
    return ans;
}
inline int les(int rt, int l, int r, int u, int w){
    if(u<=l&&r<=n) return bt[rt].less(w);
    int ans=0, mid=(l+r)>>1;
    if(u<=mid) ans+=les(rt<<1, l, mid, u, w);
    if(n>mid) ans+=les(rt<<1|1, mid+1, r, u, w);
    return ans;
}
inline void mdf(int rt, int l, int r, int u, int w){
    bt[rt].erase(h[u]), bt[rt].insert(w);
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(u<=mid) mdf(rt<<1, l, mid, u, w);
    else mdf(rt<<1|1, mid+1, r, u, w);
}

int main(){
    srand(19260817);
    in(n); for(int i=1; i<=n; ++i) in(h[i]), o[i]=h[i];
    sort(o+1, o+n+1); on=unique(o+1, o+n+1)-o-1;
    for(int i=1; i<=n; ++i){
        int cur=lower_bound(o+1, o+on+1, h[i])-o;
        add(cur, 1), res+=sum(n)-sum(cur);
    }
    outc(res);
    build(1, 1, n);
    in(m); while(m--){
        int a, b, x, y; in(a), in(b); if(a>b) swap(a, b); x=h[a], y=h[b];
        res-=mor(1, 1, n, a, h[a])+mor(1, 1, n, b, h[b]);
        res-=les(1, 1, n, a, h[a])+les(1, 1, n, b, h[b]);
        mdf(1, 1, n, a, y), mdf(1, 1, n, b, x); swap(h[a], h[b]);
        res+=mor(1, 1, n, a, h[a])+mor(1, 1, n, b, h[b]);
        res+=les(1, 1, n, a, h[a])+les(1, 1, n, b, h[b]);
        if(h[a]<h[b]) ++res;
        if(h[a]>h[b]) --res;
        outc(res);
    }
    return 0;
}