CF1830E Bully Sort 做题记录

对于排列 $\{p_i\}$，定义一次操作为按顺序执行以下步骤：

1. 令 $p_i$ 为排列中最大的满足 $p_i\neq i$ 的数；
2. 令 $p_j$ 为排列中最小的满足 $j>i$ 的数；
3. 交换 $p_i$ 和 $p_j$；
   定义 $f(p)$ 为将 $p$ 升序排序所需的操作次数。

给定一个排列 $p$，会进行 $q$ 次交换 $p_{x_i},p_{y_i}$ 的操作，每次操作后输出 $f(p)$，交换操作是永久的。

$2\le n\le 5\times 10^5$，$1\le q\le 5\times 10^4$。

人类智慧题。

考虑排序过程中一次操作对逆序对个数 $cnt$ 做出的改变，由于 $p_{[i+1,j-1]}$ 均在 $[p_i+1,p_j-1]$ 内，所以一次操作会让逆序对个数减少 $2(j-i)-1$。

接下来就很人类智慧。

首先发现 $p_i$ 这个数在排序过程中只会向它的目的地 $p_i$ 单向移动。

那么设 $sum=\sum\limits_{k=1}^n\max(p_k-k,0)$，考虑排序过程中一次操作对这个东西的影响：

• 一定有 $p_i>i$，所以 $\max(p_i-i,0)=p_i-i$；
• 一定有 $p_j\le i<j$，所以 $\max(p_j-j,0)=0$；
• 一定有 $p_j\le i$，所以 $\max(p_j-i,0)=0$；
• 一定有 $p_i\ge j$，所以 $\max(p_i-j,0)=p_i-j$；

那么一次操作让 $sum$ 减少了：

$\begin{aligned} \Delta sum&=(\max(p_i-i,0)+\max(p_j-j,0))-(\max(p_j-i,0)+\max(p_i-j,0))\\ &=(p_i-i+0)-(0+p_i-j)\\ &=j-i \end{aligned}$

发现 $\Delta cnt=2(j-i)-1$，所以 $2\Delta sum-\Delta cnt=1$。

所以 $f(p)=2sum-cnt$。

$sum$ 是很好维护的，$cnt$ 的维护相当于三维偏序，可以考虑 cdq 分治。

时间复杂度 $O(n\log ^2 n)$，代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

struct node
{
	int tme,pos,val,w;
};

const int S=500005;

int n,q,a[S];
int tot;
node que[S*2];
int c[S];
long long res[S],ans[S];

inline void addt(int p,int val)
{
	for(int i=p;i<=n;i+=i&-i) c[i]+=val;
}

inline int quet(int p)
{
	int res=0;
	for(int i=p;i>=1;i-=i&-i) res+=c[i];
	return res;
}

inline void clrt(int p)
{
	for(int i=p;i<=n;i+=i&-i) c[i]=0;
}

void cdq(int l,int r)
{
	if(l>=r) return;
	int mid=l+r>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	auto cmp=[&](node x,node y){return x.pos<y.pos;};
	sort(que+l,que+mid+1,cmp),sort(que+mid+1,que+r+1,cmp);
	int p=l;
	for(int i=mid+1;i<=r;i++)
	{
		while(p<=mid&&que[p].pos<que[i].pos) addt(n-que[p].val+1,que[p].w),p++;
		ans[que[i].tme]+=quet(n-que[i].val)*que[i].w;
	}
	for(int i=l;i<p;i++) clrt(n-que[i].val+1);
	p=mid;
	for(int i=r;i>=mid+1;i--)
	{
		while(p>=l&&que[p].pos>que[i].pos) addt(que[p].val,que[p].w),p--;
		ans[que[i].tme]+=quet(que[i].val-1)*que[i].w;
	}
	for(int i=p+1;i<=mid;i++) clrt(que[i].val);
}

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		que[++tot]=(node){0,i,a[i],true};
		res[0]+=max(a[i]-i,0);
	}
	for(int i=1;i<=q;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		que[++tot]=(node){i*2-1,x,a[x],-1};
		que[++tot]=(node){i*2-1,x,a[y],1};
		que[++tot]=(node){i*2,y,a[y],-1};
		que[++tot]=(node){i*2,y,a[x],1};
		res[i]=res[i-1];
		res[i]-=max(a[x]-x,0);
		res[i]-=max(a[y]-y,0);
		swap(a[x],a[y]);
		res[i]+=max(a[x]-x,0);
		res[i]+=max(a[y]-y,0);
	}
	cdq(1,tot);
	for(int i=1;i<=q*2;i++) ans[i]+=ans[i-1];
	for(int i=1;i<=q;i++) printf("%lld\n",2*res[i]-ans[i*2]);
	return 0;
}