题目大意：给定一个序列，m次交换两个数，求初始逆序对数及每次交换后的逆序对数
首先离散化，分块，对于每块建立一个树状数组，保存这个块中的所有元素
然后对于每个询问(x,y) (x<y) 两侧的数是没有影响的，区间(x,y)的数a[i]讨论如下：
a[i]<a[x] --ans
a[i]>a[x] ++ans
a[i]<a[y] ++ans
a[i]>a[y] --ans
然后对于块中的树状数组处理，块外的暴力
注意此题元素有重复 亲测可信
RANK5吓尿0.0 为何块套树要比树套树还快……
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 20200
using namespace std;
int n,m,ans,tot,block,a[M];
pair<int,int>b[M];
int pre[M],cnt[200][M];
void Update(int c[],int x)
{
for(;x<=n;x+=x&-x)
++c[x];
}
void Downdate(int c[],int x)
{
for(;x<=n;x+=x&-x)
--c[x];
}
int Get_Ans(int c[],int x)
{
int re=0;
for(;x;x-=x&-x)
re+=c[x];
return re;
}
int main()
{
int i,j,x,y;
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&b[i].first),b[i].second=i;
sort(b+1,b+n+1);
for(i=1;i<=n;i++)
{
if(b[i].first!=b[i-1].first)
++tot;
a[b[i].second]=tot;
}
for(i=n;i;i--)
ans+=Get_Ans(pre,a[i]-1),Update(pre,a[i]);
block=static_cast<int>(sqrt(n)+1e-7);
for(i=1;i<=n;i++)
Update(cnt[(i-1)/block],a[i]);
cout<<ans<<endl;
cin>>m;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
//查询(x,y)区间内有多少个数比a[x]和a[y]小
int b1=(x-1)/block+1;
int b2=(y-1)/block-1;
if(b1<=b2)
{
for(j=b1;j<=b2;j++)
{
ans-=Get_Ans(cnt[j],a[x]-1);
ans+=Get_Ans(cnt[j],n)-Get_Ans(cnt[j],a[x]);
ans+=Get_Ans(cnt[j],a[y]-1);
ans-=Get_Ans(cnt[j],n)-Get_Ans(cnt[j],a[y]);
}
for(j=x+1;j<=b1*block;j++)
{
if(a[j]<a[x]) --ans;
if(a[j]>a[x]) ++ans;
if(a[j]<a[y]) ++ans;
if(a[j]>a[y]) --ans;
}
for(j=(b2+1)*block+1;j<y;j++)
{
if(a[j]<a[x]) --ans;
if(a[j]>a[x]) ++ans;
if(a[j]<a[y]) ++ans;
if(a[j]>a[y]) --ans;
}
}
else
{
for(j=x+1;j<=y-1;j++)
{
if(a[j]<a[x]) --ans;
if(a[j]>a[x]) ++ans;
if(a[j]<a[y]) ++ans;
if(a[j]>a[y]) --ans;
}
}
if(a[x]<a[y]) ++ans;
else if(a[x]>a[y]) --ans;
printf("%d\n",ans);
Downdate(cnt[(x-1)/block],a[x]);
Downdate(cnt[(y-1)/block],a[y]);
swap(a[x],a[y]);
Update(cnt[(x-1)/block],a[x]);
Update(cnt[(y-1)/block],a[y]);
}
}