【Codeforces 785E】Anton and Permutation
分块
题目大意：
给定一个排列，初始位置 $i$ 的值为 $i$。有 $m$ 次操作，每次操作交换两个元素，问每次操作完后的逆序对个数。
题解：
线性空间的不带 $\log$ 的根号做法。
数列分块，同时值域分块。令 $g[x][y]$ 表示数列上的前 $x$ 个块中（包括第 $x$ 个），值域范围在第 $y$ 个块中的数的个数。令 $pos[i]$ 表示数 $i$ 在数列中的位置。
$g$ 数组的初始值十分有规律，因此预处理可以直接 $O(n)$。
交换两个数，显然需要考虑中间那些数对它们贡献的。由于排列没有重复元素，所以如果 $[l+1,r-1]$ 中（$l+1\leqslant r-1$）有 $k$ 个数小于 $a_l$，那么就有 $r-l-1-k$ 个数大于 $a_l$。当 $a_l$ 移到后面时，逆序对的个数就会增加 $r-l-1-k$，并减少 $k$。$a_r$ 的贡献变化同理。最后不要忘记 $a_l$ 与 $a_r$ 的贡献。
那么我们相当于要求区间 $[l,r]$ 内小于（小于等于）$k$ 的数的个数。
已经对序列进行分块。边角的贡献暴力统计。对于中间的部分，我们可以通过 $g$ 数组前缀相减，得到某一个值域块内的所有数在中间这段的出现总次数。
那么枚举值域块，把贡献累加即可。当剩下的可能的数值不满整块的时候，直接暴力判断这个数在数列中的位置是否在统计的这部分里即可。
单次查询的时间复杂度为 $O(\sqrt n)$。
考虑两个数交换需要对 $g$ 进行修改，由于块的个数为 $\sqrt n$，所以总共需要修改的数的个数不超过 $2\sqrt n$。单次时间复杂度 $O(\sqrt n)$。
总时间复杂度 $O(m\sqrt n)$。空间复杂度 $O(n)$。
Code：
#include<iostream>
#include<algorithm>
using namespace std;
#define bel(x)((x-1)/siz+1)
const int siz=600,N=2e5+2;
typedef long long LL;
int g[N/siz+2][siz+2],n,q,blocks;
int a[N],L[N/siz+2],R[N/siz+2],pos[N];
LL ans;
inline int ask(int l,int r,const int val){
if(l>r)return 0;
int bL=bel(l),bR=bel(r);
int ret=0;
if(bL==bR){
for(int i=l;i<=r;++i)ret+=a[i]<=val;
return ret;
}else{
for(int i=l;i<=R[bL];++i)ret+=a[i]<=val;
for(int i=L[bR];i<=r;++i)ret+=a[i]<=val;
l=L[bL+1],r=R[bR-1];
if(bL<--bR){
for(int i=1;;++i)
if(i*siz<=val)ret+=g[bR][i]-g[bL][i];else{
for(int j=(i-1)*siz+1;j<=val;++j)
ret+=l<=pos[j]&&pos[j]<=r;
break;
}
}
return ret;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q;
blocks=bel(n);
for(int i=1;i<=blocks;++i)L[i]=R[i-1]+1,R[i]=i*siz;R[blocks]=n;
for(int i=1;i<=n;++i)a[i]=pos[i]=i;
for(int i=1;i<blocks;++i)
for(int j=i;j<=blocks;++j)g[j][i]=siz;
g[blocks][blocks]=n-L[blocks]+1;
while(q--){
int l,r;
cin>>l>>r;
if(l>r)l^=r^=l^=r;
if(l==r){
cout<<ans<<'\n';
continue;
}
int len=r-l+1-2,dlt1=ask(l+1,r-1,a[l]),dlt2=ask(l+1,r-1,a[r]);
ans=ans-dlt1*2+dlt2*2;
if(a[l]<a[r])++ans;else --ans;
for(int i=bel(l);i<bel(r);++i)--g[i][bel(a[l])],++g[i][bel(a[r])];
swap(a[l],a[r]);
pos[a[l]]=l,pos[a[r]]=r;
cout<<ans<<'\n';
}
return 0;
}