用整体二分写的，求大佬给个hack QwQ 从80打成75又打成0分qwq

#include<bits/stdc++.h>
#define int long long
#define N 5123456
#define inf 2147483647121
#define lowbit(x) ((x)&(-x))
using namespace std ;
int n , m , cnt=0 , ans[N] , num[N] , tr1[N] , tr2[N] , real_ans=0 , q=0 ;
struct node{
	int x , k , opt , i , number , l , r ;
}a[N],q1[N],q2[N],temp[N];
void change(int tr[],int x,int k){
	while(x<=n){
		tr[x] += k ;
		x += lowbit(x) ;
	}
}
int ask(int tr[],int x){
	int ans=0 ;
	while(x){
		ans += tr[x] ;
		x -= lowbit(x) ;
	}
	return ans ;
}
void solve(int l,int r,int L,int R){
	if(L>R) return ;
	if(l>=r) return ;
	int mid=(l+r)>>1 , tot1=0 , tot2=0 ;
	for(int i=L;i<=R;i++){
		if(a[i].opt==1){
			if(mid>=a[i].x) change(tr1,a[i].number,a[i].k) , q1[++tot1] = a[i] ;   //插入小于 
			else q2[++tot2] = a[i] ;              //插入大于
		}else if(a[i].opt==2){    						//逆序对 
			if(mid>=a[i].x) q1[++tot1] = a[i] ; 
			else{															   
				ans[a[i].i] += ask(tr1,n)-ask(tr1,a[i].number-1) ;
				q2[++tot2] = a[i] ;
			}
		}else if(a[i].opt==3){							//排名 
			if(mid>=a[i].x) q1[++tot1] = a[i] ;
			else{
				ans[a[i].i] += ask(tr1,a[i].r)-ask(tr1,a[i].l-1) ;
				q2[++tot2] = a[i] ;
			}
		}
	}
	for(int i=1;i<=tot1;i++){
		a[i+L-1] = q1[i] ;
		if(q1[i].opt==1) change(tr1,q1[i].number,-q1[i].k) ;
	}
	for(int i=1;i<=tot2;i++) a[i+L+tot1-1] = q2[i] ;
	solve(l,mid,L,L+tot1-1) ;
	solve(mid+1,r,L+tot1,R) ;
}
void solve1(int l,int r,int L,int R){
	if(L>R) return ;
	if(l>=r) return ;
	int mid=(l+r)>>1 , tot1=0 , tot2=0 ;
	for(int i=L;i<=R;i++){
		if(a[i].opt==1){
			if(mid>a[i].x) q1[++tot1] = a[i] ;   //插入小于 
			else change(tr2,a[i].number,a[i].k) , q2[++tot2] = a[i] ;              //插入大于
		}else if(a[i].opt==4){							//跟排名有点像的神奇东西…… 
			if(mid<=a[i].x) q2[++tot2] = a[i] ;
			else{
				ans[a[i].i] += ask(tr2,a[i].r)-ask(tr2,a[i].l-1) ;
				q1[++tot1] = a[i] ;
			}
		}else q1[++tot1] = a[i] ;
	}
	for(int i=1;i<=tot1;i++) a[i+L-1] = q1[i] ;
	for(int i=1;i<=tot2;i++){
		a[i+L+tot1-1] = q2[i] ;
		if(q2[i].opt==1) change(tr2,q2[i].number,-q2[i].k) ;
	}
	solve1(l,mid,L,L+tot1-1) ;
	solve1(mid+1,r,L+tot1,R) ;
}
signed main(){
//	freopen("1.in","r",stdin) ;
//	freopen("2.out","w",stdout) ;
	cin >> n ;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i].x) , a[i].k = 1 , a[i].opt = 1 , num[i] = a[i].x , a[i].number = i ; 
	cnt = n ;
	for(int i=1;i<=n;i++){
		a[++cnt].opt = 2 ;
		a[cnt].i = i , a[cnt].number = i , a[cnt].x = num[i] ;
	}
	q = n ;
	cin >> m ;
	for(int i=1;i<=m;i++){
		int x , y ;
		scanf("%lld%lld",&x,&y) ;
		if(x>y) swap(x,y) ;
		a[++cnt].opt = 3 ;
		a[cnt].l = x , a[cnt].r = y-1 , a[cnt].i = ++q , a[cnt].x = num[x] ;
		if(num[x]>num[y]) ans[q]++ ;
		else if(num[x]<num[y]) ans[q]-- ;
		a[++cnt].opt = 4 ;
		a[cnt].l = x , a[cnt].r = y-1 , a[cnt].i = ++q , a[cnt].x = num[x] ; 
		a[++cnt].opt = 3 ;
		a[cnt].l = x+1 , a[cnt].r = y , a[cnt].i = ++q , a[cnt].x = num[y] ;
		a[++cnt].opt = 4 ;
		a[cnt].l = x+1 , a[cnt].r = y , a[cnt].i = ++q , a[cnt].x = num[y] ;
		a[++cnt].opt = 1 ;
		a[cnt].x = num[x] , a[cnt].k = -1 , a[cnt].number = x ;
		a[++cnt].opt = 1 ;
		a[cnt].x = num[y] , a[cnt].k = -1 , a[cnt].number = y ;
		a[++cnt].opt = 1 ;
		a[cnt].x = num[x] , a[cnt].k = 1 , a[cnt].number = y ;
		a[++cnt].opt = 1 ;
		a[cnt].x = num[y] , a[cnt].k = 1 , a[cnt].number = x ;
		swap(num[x],num[y]) ;
	}
	for(int i=1;i<=cnt;i++) temp[i] = a[i] ;
	solve(-inf,inf,1,cnt) ;
	for(int i=1;i<=cnt;i++) a[i] = temp[i] ;
	solve1(-inf,inf,1,cnt) ;
	for(int i=1;i<=n;i++) real_ans += ans[i]  ;
	printf("%lld\n",real_ans) ;
	for(int i=n+1;i<=q;i+=4){
		real_ans += -ans[i]+ans[i+1]+ans[i+2]-ans[i+3] ;
		printf("%lld\n",real_ans) ;
//		printf("%lld %lld %lld %lld\n",ans[i],ans[i+1],ans[i+2],ans[i+3]) ; 
	}
	return 0 ;
}