BZOJ2141 排队 树状数组 分块

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ2141.html

题目传送门 - BZOJ2141

题意

　　给定一个序列 $a$ ，先输出原先的逆序对数。

　　然后 $m$ 次操作，每次交换两个数，并输出交换后的逆序对数。

　　$1≤m≤2\times 10^3，1≤n≤2\times 10^4，1≤a_i≤10^9$

题解

　　离散化。

　　分个块。

　　对于每一个前缀块和后缀块搞一个树状数组，维护一下每种值的个数的前缀和。

　　考虑删除和增加操作，就是修改块内信息和统计块内块外信息。

　　统计块内信息直接暴力。

　　统计块外信息通过预处理的前缀块和后缀块树状数组来快速搞定。

　　可以写一个子程序把四个东西压起来。

　　但是我这样的做法需要注意一点：交换的两个数字在同一块内的时候，贡献会被算两遍。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=20005;

int n,m,a[N],Ha[N],hs;

int Lv[45][N],Rv[45][N];

void HASH(){

	sort(Ha+1,Ha+n+1);

	hs=1;

	for (int i=2;i<=n;i++)

		if (Ha[i]!=Ha[i-1])

			Ha[++hs]=Ha[i];

}

void add(int *c,int x,int d){

	for (;x<=hs;x+=x&-x)

		c[x]+=d;

}

int sum(int *c,int x){

	int ans=0;

	for (;x>0;x-=x&-x)

		ans+=c[x];

	return ans;

}

int Solve0(int *c,int *a,int n){

	int ans=0;

	for (int i=1;i<=n;i++){

		ans+=sum(c,hs)-sum(c,a[i]);

		add(c,a[i],1);

	}

	return ans;

}

int update(int x,int d){

	int y=((x-1)>>10)+1,L=((y-1)<<10)+1,R=min(y<<10,n);

	int ans=sum(Lv[y],hs)-sum(Lv[y],a[x])+sum(Rv[y],a[x]-1);

	for (int i=L;i<x;i++)

		if (a[i]>a[x])

			ans++;

	for (int i=R;i>x;i--)

		if (a[i]<a[x])

			ans++;

	for (int i=1;i<y;i++)

		add(Rv[i],a[x],d);

	for (int i=y+1;((i-1)<<10)<n;i++)

		add(Lv[i],a[x],d);

	return ans*d;

}

int main(){

	scanf("%d",&n);

	for (int i=1;i<=n;i++)

		scanf("%d",&a[i]),Ha[i]=a[i];

	HASH();

	for (int i=1;i<=n;i++)

		a[i]=lower_bound(Ha+1,Ha+hs+1,a[i])-Ha;

	int ans=Solve0(Lv[0],a,n);

	memset(Lv,0,sizeof Lv);

	memset(Rv,0,sizeof Rv);

	for (int i=1;((i-1)<<10)<n;i++){

		int L=((i-1)<<10)+1,R=min(i<<10,n);

		for (int j=1;j<L;j++)

			add(Lv[i],a[j],1);

		for (int j=n;j>R;j--)

			add(Rv[i],a[j],1);

	}

	scanf("%d",&m);

	printf("%d\n",ans);

	while (m--){

		int x,y;

		scanf("%d%d",&x,&y);

		if (x>y)

			swap(x,y);

		ans+=update(x,-1);

		ans+=update(y,-1);

		if (((x-1)>>10)==((y-1)>>10)){

			if (a[x]>a[y])

				ans++;

			if (a[y]>a[x])

				ans--;

		}

		swap(a[x],a[y]);

		ans+=update(x,1);

		ans+=update(y,1);

		printf("%d\n",ans);

	}

	return 0;

}