【2025广东省队集训day1】排列 做题记录

给定一个 $n$ 的排列 $p$，两点 $i,j$ 之间存在无向边当且仅当 $i<j$ 且 $p_i>p_j$（即逆序对），定义 $\text{dis}(x,y)$ 表示 $x$ 和 $y$ 之间的最短路的长度（不连通则为 $0$），对于每一个 $i$ 求 $\sum\limits_{j=1}^n \text{dis}(i,j)$。
$1\le n\le 2\times 10^5$。

对于一个点 $i$，考虑距离 $i$ 为 $1,2,3,\dots$ 的点都在哪里：（只考虑左下角，右上角同理）

其中 $dwn$ 是右边的最小的 $p_i$，$lft$ 是上面的最左的 $i$。

不难发现可以使用 $dwn$ 和 $lft$ 的交点来刻画。具体的，设 $lft_i$ 为 $p_j\ge i$ 的最小的 $j$，$dwn_i$ 为 $j\ge i$ 的最小的 $p_j$，从 $(i,p_i)$ 开始不断跳跃，其中 $(x,y)$ 会跳到 $(lft_y,dwn_x)$，这样就能找到所有的关键点（图中的三角形），从而在每个关键点处再做一次二位偏序就可以求出答案。

接下来我们来证明一个关键结论：

从每个 $(i,p_i)$ 开始跳，将途中的二元组 $(x,y)$ 放入一个集合 $S$ 中（称为关键点集合），那么 $|S|$ 是 $O(n\sqrt n)$ 级别的。

有了这个结论就好做了，找到所有关键点后用 $O(\sqrt n)$ 单点加 $O(1)$ 前缀查询的分块做二维偏序，然后按照跳的顺序扫一遍所有关键点即可递推出答案。

找所有关键点可以用哈希表维护暴力跳，但是常数比较大。

一个较好的写法是注意到每个起点 $x$ 对应的 $pos_{dwn_x}$ 是递增的（$pos_i$ 为 $i$ 在 $p$ 中出现的位置）。那么考虑 $x$ 从 $n$ 扫到 $1$，扫的时候对于每个 $i$ 维护第一维为 $i$ 的所有关键点的第二维 $s_i$。扫到 $x$ 的时候在 $s_x$ 末尾加入 $p_x$，再扫一次 $s_x$，将所有 $(x,y)|y\in s_x$ 跳到的点加入对应的 $s$ 中。这样每次新加入的 $(x,y)$ 一定满足 $\forall z\in s_x,pos_y<pos_z$，所以直接判断其是否和 $s_x$ 的末尾相同即可。

注意有可能出现 $(x,y)$ 跳一下跳到 $(x,dwn_x)$ 的情况，所以每个 $x$ 有一个关键点要提前单独做。

注意别忘了正反做两次。

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

#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <vector>

using namespace std;

typedef long long ll;

const int S=200005,B=450;

int n,p[S],pos[S];
int dwn[S],lft[S];
vector<pair<int,int> > vec[S];
int pt[S],idx[S];
vector<pair<int,pair<ll,int> > > f[S];
int tag[S/B+5],sm[S];
ll ans[S];

inline void addt(int p,int x){for(int i=p;i<=n;i+=i&-i) sm[i]+=x;}
inline int quet(int p)
{
	int res=0;
	for(int i=p;i>=1;i-=i&-i) res+=sm[i];
	return res;
}

inline void add(int p,int x)
{
	int id=(p-1)/B+1;
	for(int i=p;i<=id*B&&i<=n;i++) sm[i]+=x;
	for(int i=id+1;i<=(n-1)/B+1;i++) tag[i]+=x;
}
inline int que(int p)
{
	int id=(p-1)/B+1;
	return tag[id]+sm[p];
}

inline int inspot(int x,int y)
{
	if(vec[x].empty()||vec[x].back().first!=y)
		vec[x].emplace_back(y,-1);
	return vec[x].size()-1;
}

inline void doit()
{
	for(int i=1;i<=n;i++) sm[i]=0;
	for(int i=1;i<=(n-1)/B+1;i++) tag[i]=0;
	for(int i=1;i<=n;i++) vec[i].clear(),f[i].clear();
	for(int i=1;i<=n;i++) pos[p[i]]=i;
	dwn[n]=p[n];
	for(int i=n-1;i>=1;i--) dwn[i]=min(dwn[i+1],p[i]);
	lft[n]=pos[n];
	for(int i=n-1;i>=1;i--) lft[i]=min(lft[i+1],pos[i]);
	for(int x=n;x>=1;x--)
	{
		int y=p[x];
		pt[x]=inspot(x,dwn[x]);
		idx[x]=inspot(x,y);
		for(auto &t:vec[x])
		{
			int y=t.first,&id=t.second;
			int nx=lft[y],ny=dwn[x];
			if(nx==x&&ny==y) continue;
			if(nx!=x) id=inspot(nx,ny);
			else id=pt[x];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(auto t:vec[i])
			f[i].emplace_back(que(t.first),make_pair(0,0));
		add(p[i],1);
	}
	for(int x=1;x<=n;x++)
	{
		int i=pt[x];
		int nx=lft[vec[x][i].first],id=vec[x][i].second;
		auto &cur=f[x][i];
		if(id!=-1)
		{
			auto tt=f[nx][id];
			ll ans=tt.second.first;
			int cnt=tt.second.second;
			ans+=cnt;
			int pre=cur.first-tt.first;
			ans+=pre*2;
			cnt+=pre;
			cur.second=make_pair(ans,cnt);
		}
		int sz=vec[x].size();
		for(int i=0;i<sz;i++)
		{
			int nx=lft[vec[x][i].first],id=vec[x][i].second;
			auto &cur=f[x][i];
			if(id!=-1)
			{
				auto tt=f[nx][id];
				ll ans=tt.second.first;
				int cnt=tt.second.second;
				ans+=cnt;
				int pre=cur.first-tt.first;
				ans+=pre*2;
				cnt+=pre;
				cur.second=make_pair(ans,cnt);
			}
		}
		ans[x]+=f[x][idx[x]].second.first;
	}
}

int main()
{
	freopen("permutation.in","r",stdin);
	freopen("permutation.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i];
	for(int i=1;i<=n;i++)
	{
		ans[i]+=quet(n-p[i]+1);
		addt(n-p[i]+1,1);
	}
	for(int i=1;i<=n;i++) sm[i]=0;
	for(int i=n;i>=1;i--)
	{
		ans[i]+=quet(p[i]);
		addt(p[i],1);
	}
	doit();
	for(int i=1;i<=n;i++) p[i]=n-p[i]+1;
	for(int i=1;i<=n/2;i++) swap(p[i],p[n-i+1]),swap(ans[i],ans[n-i+1]);
	doit();
	for(int i=1;i<=n/2;i++) swap(ans[i],ans[n-i+1]);
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
	cout<<'\n';
	return 0;
}