分块求助，自测随机大样例能过

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
#define INF 200005
using namespace std;

int n,m;
int len,upl;
int bel[INF];
int h[INF],a[INF],b[INF];
int tree[INF];

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
	write(x/10);
	putchar(x%10+'0');
}
int ls(int x)
{
	return (x-1)*len+1;
}
int rs(int x)
{
	return x*len;
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
		tree[i]+=k;
}
int query(int x)
{
	int ret=0;
	for(int i=x;i;i-=lowbit(i))
		ret+=tree[i];
	return ret;
}

//获取区间[l,r]内比x大的数的个数 
int getu(int l,int r,int x)
{
	if(l>r)
		return 0;
	int ret=0;
	if(bel[l]==bel[r])
	{
		for(int i=l;i<=r;i++)
		{
			if(a[i]>x)
				ret++;
		}
		return ret;
	}
	
	for(int i=l;i<=rs(bel[l]);i++)
	{
		if(a[i]>x)
			ret++;
	}
	for(int i=ls(bel[r]);i<=r;i++)
	{
		if(a[i]>x)
			ret++;
	}
	//块内采用二分找 
	int pos=0;
	for(int i=bel[l]+1;i<=bel[r]-1;i++)
	{
		pos=upper_bound(b+ls(i),b+rs(i)+1,x)-b;
		ret+=rs(i)-pos+1;
	}
	return ret;
}
//获取区间[l,r]内比x小的数的个数 
int getd(int l,int r,int x)
{
	if(l>r)
		return 0;
	int ret=0;
	if(bel[l]==bel[r])
	{
		for(int i=l;i<=r;i++)
		{
			if(a[i]<x)
				ret++;
		}
		return ret;
	}
	
	for(int i=l;i<=rs(bel[l]);i++)
	{
		if(a[i]<x)
			ret++;
	}
	for(int i=ls(bel[r]);i<=r;i++)
	{
		if(a[i]<x)
			ret++;
	}
	int pos=0;
	for(int i=bel[l]+1;i<=bel[r]-1;i++)
	{
		pos=lower_bound(b+ls(i),b+rs(i)+1,x)-b;
		ret+=pos-ls(i);
	}
	return ret;
}
//交换x和y位置的元素 
void tran(int x,int y)
{
	//pos1 pos2找到b数组对应值然后更改 
	int pos1=lower_bound(b+ls(bel[x]),b+rs(bel[x])+1,a[x])-b;
	int pos2=lower_bound(b+ls(bel[y]),b+rs(bel[y])+1,a[y])-b;
	b[pos1]=a[y];b[pos2]=a[x];
	//b数组重新排序 
	sort(b+ls(bel[x]),b+rs(bel[x])+1);
	sort(b+ls(bel[y]),b+rs(bel[y])+1);
	//交换a数组 
	swap(a[x],a[y]);
}
signed main()
{
	//输入 
	n=read();
	for(int i=1;i<=n;i++)
	{
		h[i]=read();
		a[i]=h[i];
	}	
	
	//离散化 
	sort(h+1,h+n+1);
	int l=unique(h+1,h+n+1)-h-1;
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(h+1,h+l+1,a[i])-h;
		b[i]=a[i];
	}
	
	//树状数组求初始逆序对 
	int ans=0;
	for(int i=n;i>=1;i--)
	{
		ans+=query(a[i]-1);
		add(a[i],1);
	}
	write(ans);
	putchar('\n');
	
	//分块 
	len=sqrt(n);
	for(int i=1;i<=n;i++)
		bel[i]=(i-1)/len+1;
	upl=bel[n];
	//末尾赋值最大值，交换时防止最后一个块出错 
	for(int i=n+1;i<=rs(bel[n]);i++)
		a[i]=b[i]=1e18;
	for(int i=1;i<=n;i+=len)
		sort(b+i,b+i+len);
	
	m=read();
	int x,y;
	int t1,t2,t3,t4;
	for(int i=1;i<=m;i++)
	{
		x=read();y=read();
		if(x>y)
			swap(x,y);
		//对本次操作进行维护 
		t1=getu(x+1,y-1,a[x]);t2=getd(x+1,y-1,a[x]);
		ans+=t1;ans-=t2;
		t3=getu(x+1,y-1,a[y]);t4=getd(x+1,y-1,a[y]);
		ans+=t4;ans-=t3;
		//两个断点判断 
		if(a[x]>a[y])
			ans--;
		else if(a[x]<a[y])
			ans++;
		//交换 
		tran(x,y);
		write(ans);
		putchar('\n');
	}
	
	return 0;
}