Codeforces 785 E. Anton and Permutation
题目大意：给出n，q。n代表有一个元素从1到n的数组（对应索引1~n)，q表示有q个查询。每次查询给出两个数l，r，要求将索引为l,r的两个数交换位置，并给出交换后数组中的逆序对数。
思路：此题用到了分块的思想，即将这组数分为bsz块，在每一块上建Fenwick树，对于每次查询，只需要处理l，r中间的块和l，r所在块受影响的部分。具体实现见代码及注释。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> M;
typedef queue<int> Q;
typedef set<int> S;
typedef vector<int> V;
const int maxn=2e5+10,bsz=2000;
int n;
int br[maxn],bl[maxn],b[maxn]; //br[i]为编号为i块的右界，bl[i]为编号为i块的左界，b[i]为i点对应的块编号
struct fenwick
{
int sum[maxn];
void add(int p,int x)
{
while (p<=n)
{
sum[p]+=x;
p+=p&-p;
}
}
int qry(int p)
{
int res=0;
while (p)
{
res+=sum[p];
p-=p&-p;
}
return res;
}
} fen[maxn/bsz+1];
int a[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int i,j,m,q;
cin>>n>>q;
//分块、定界
int bn=(n-1)/bsz+1;
for (i=0;i<bn;++i)
{
bl[i]=i*bsz;
br[i]=min(n,i*bsz+bsz);
for (j=bl[i];j<br[i];++j)
b[j]=i;
}
//数据初始化，上树
for (i=0;i<n;++i)
{
a[i]=i+1;
fen[b[i]].add(a[i],1);
}
//处理query
ll ans=0;
while (q--)
{
int l,r;
cin>>l>>r;
l--;
r--;
if (l==r)
{
cout<<ans<<endl;
continue;
}
else if (l>r)
swap(l,r);
int less_l=0,less_r=0;
//处理l,r中间的块
for (i=b[l]+1;i<b[r];++i)
{
less_l+=fen[i].qry(a[l]);
less_r+=fen[i].qry(a[r]);
}
//处理l,r所在块的影响部分
if (b[l]!=b[r])
{
for (i=l;i<br[b[l]];++i)
{
less_l+=a[i]<a[l];
less_r+=a[i]<a[r];
}
for (i=bl[b[r]];i<=r;++i)
{
less_l+=a[i]<a[l];
less_r+=a[i]<a[r];
}
}
else
{
for (i=l;i<=r;++i)
{
less_l+=a[i]<a[l];
less_r+=a[i]<a[r];
}
}
//由于计算less_l和less_r时，对于端点l,r的处理有重复计数，因此需要修正答案
if (a[l]<a[r])
ans--;
else
ans++;
//更新Fenwick树
fen[b[l]].add(a[l],-1);
fen[b[r]].add(a[r],-1);
swap(a[l],a[r]);
fen[b[l]].add(a[l],1);
fen[b[r]].add(a[r],1);
//处理答案
int total=r-l;
ll tmpl=(total-less_l)-less_l;//增加的逆序对数-减少的逆序对数
ll tmpr=less_r-(total-less_r); //增加的逆序对数-减少的逆序对数
ans+=tmpl+tmpr;
cout<<ans<<endl;
}
return 0;
}