自己想了一个树套树做法，但是还是wa，55pts。

#include<bits/stdc++.h>
#define N 20010
#define endl '\n'
#define I_love_Furina return
#define forever 0
#define foreverr 1
#define db double
#define ldb long double
#define mid (l+r>>1)
#define lb(x) (-x&x)
//#define int long long
using namespace std;
int n,m,T,rt[N],y[N],t[N],rot,ans=0,num;
struct node{int siz,ls,rs;}a[N*400];
unordered_map<int,int> mp;
inline void add(int x,int val){while(x<=num)rt[x]+=val,x+=lb(x);}
inline int sum(int x){int rp=0;while(x)rp+=rt[x],x-=lb(x);I_love_Furina rp;}
inline void init(){for(int i=1;i<=n;i++)ans+=i-1-sum(mp[y[i]]),add(mp[y[i]],1);}
int update(int p,int l,int r,int k,int val){
    int pr=++rot;
    a[pr]=a[p],a[pr].siz+=val;
    if(l==r)I_love_Furina pr;
    if(mid>=k)a[pr].ls=update(a[pr].ls,l,mid,k,val);
    else a[pr].rs=update(a[pr].rs,mid +1,r,k,val);
    I_love_Furina pr;
}
inline void pre_update(int x,int val){
    int k=mp[y[x]];
    
    while(x<=n)rt[x]=update(rt[x],1,num,k,val),x+=lb(x);
}
int query(int p,int l,int r,int k){
   if(l==r)I_love_Furina forever;
   int ans=0;
   if(k>mid)I_love_Furina a[a[p].ls].siz+query(a[p].rs,mid+1,r,k);
   else I_love_Furina query(a[p].ls,l,mid,k); 
}
inline int pre_query(int l,int r,int x){
    int sum=0;
    l--;
    while(r)sum+=query(rt[r],1,num,mp[x])-(a[rt[r]].siz-query(rt[r],1,num,mp[x]+1)),r-=lb(r);
    //cout<<sum<<":";
    while(l)sum-=query(rt[l],1,num,mp[x])-(a[rt[l]].siz-query(rt[l],1,num,mp[x]+1)),l-=lb(l);
    //cout<<sum<<endl;
    I_love_Furina sum;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
    for(int i=1;i<=n;i++)cin>>y[i],t[++num]=y[i];
    sort(t+1,t+num+1),num=unique(t+1,t+num+1)-t-1;
    for(int i=1;i<=num;i++)mp[t[i]]=i;
    init();
    memset(rt,0,sizeof rt);
    for(int i=1;i<=n;i++)pre_update(i,1);
    cout<<ans<<endl;
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        ans+=pre_query(l+1,r-1,y[r]);
        ans-=pre_query(l+1,r-1,y[l]);
        if(y[l]>y[r])ans--;
        else ans++;
        pre_update(r,-1),pre_update(l,-1);
        swap(y[l],y[r]);
        pre_update(l,1),pre_update(r,1);
        cout<<ans<<endl;
    }
	I_love_Furina forever;
}