题目大意：略
和 [CQOI2015]动态逆序对 这道题一样的思路
一开始的序列视为$n$次插入操作
把每次交换操作看成四次操作，删除$x$，删除$y$，加入$x$，加入$y$
把每次操作都看成一个三元组 $<x,w,t>$ 操作位置，权值，以及操作时间
变成了一道三维偏序裸题
外层按操作时间$t$升序，回溯时按操作位置$x$排序
处理左区间对右区间的影响时，正反两次树状数组求逆序对即可
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 30100
#define ll long long
#define dd double
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,m,ma,nn,K; struct BIT{
int s[N1];
void update(int x,int w){for(int i=x;i<=ma;i+=(i&(-i))) s[i]+=w;}
int query(int x){int ans=; for(int i=x;i;i-=(i&(-i))) ans+=s[i]; return ans;}
}b;
struct node{int p,x,w,t,ans;}a[N1],tmp[N1];
int c[N1],q[N1],que[N1],tl; void CDQ(int L,int R)
{
if(R-L<=) return;
int M=(L+R)>>;
CDQ(L,M); CDQ(M,R);
int i=M-,j=R-,cnt=,x;
while(i>=L&&j>=M)
{
if(a[i].x>a[j].x){
b.update(a[i].w,a[i].p);
que[++tl]=i; i--;
}else{
a[j].ans+=b.query(a[j].w-);
j--;
}
}
while(i>=L) {i--;}
while(j>=M) {a[j].ans+=b.query(a[j].w-); j--;}
while(tl) {x=que[tl--]; b.update(a[x].w,-a[x].p);} i=L,j=M,cnt=;
while(i<M&&j<R)
{
if(a[i].x<=a[j].x){
b.update(a[i].w,a[i].p);
que[++tl]=i; tmp[++cnt]=a[i]; i++;
}else{
a[j].ans+=b.query(ma)-b.query(a[j].w);
tmp[++cnt]=a[j]; j++;
}
}
while(i<M) {tmp[++cnt]=a[i]; i++;}
while(j<R) {a[j].ans+=b.query(ma)-b.query(a[j].w); tmp[++cnt]=a[j]; j++;}
while(tl) {x=que[tl--]; b.update(a[x].w,-a[x].p);} for(i=L;i<R;i++) a[i]=tmp[i-L+];
}
int cmp(node s1,node s2){return s1.t<s2.t;} int main()
{
scanf("%d",&n);
int i,j,x,y; ll ans=;
for(i=;i<=n;i++) c[i]=a[i].w=gint();
sort(c+,c+n+);
ma=unique(c+,c+n+)-(c+);
for(i=;i<=n;i++) a[i].w=lower_bound(c+,c+ma+,a[i].w)-c,q[i]=a[i].w;
for(i=;i<=n;i++) a[i].p=,a[i].t=i,a[i].x=i;
for(i=n;i>=;i--) ans+=b.query(a[i].w-),b.update(a[i].w,);
memset(b.s,,sizeof(b.s));
scanf("%d",&m); nn=n;
for(i=n+;i<=n+m;i++)
{
x=gint(); y=gint();
a[++nn].p=-,a[nn].t=nn,a[nn].x=x,a[nn].w=q[x];//,a[nn].id=i-n;
a[++nn].p=-,a[nn].t=nn,a[nn].x=y,a[nn].w=q[y];//a[nn].id=i-n;
swap(q[x],q[y]);
a[++nn].p=,a[nn].t=nn,a[nn].x=x,a[nn].w=q[x];//a[nn].id=i-n;
a[++nn].p=,a[nn].t=nn,a[nn].x=y,a[nn].w=q[y];//a[nn].id=i-n;
}
CDQ(,nn+);
sort(a+,a+nn+,cmp);
printf("%lld\n",ans);
for(i=n+;i<=nn;i+=)
{
ans+=-a[i].ans-a[i+].ans+a[i+].ans+a[i+].ans;
printf("%lld\n",ans);
}
return ;
}