AT_abc283_f [ABC283F] Permutation Distance 题解

分析

分类讨论。

对 \(|p_i-p_j|+|i-j|\) 分类讨论，有：

1. \((p_i+i)-(p_j+j)\)，\(p_i>p_j \land i>j\)。
2. \(-(p_i-i)+(p_j-j)\)，\(p_i<p_j \land i>j\)。
3. \((p_i-i)-(p_j-j)\)，\(p_i>p_j \land i<j\)。
4. \(-(p_i+i)+(p_j+j)\)，\(p_i<p_j \land i<j\)。

然后用树状数组跑取最小值就行了。可以开两个树状数组，\(1,3\) 情况一个;\(2,4\) 情况一个。因为要使 \(d_i\) 小，而在式子的左半部分一定时，\(1,3\) 情况的右半部分都是减一个值，所以第一个树状数组维护最大值；\(2,4\) 情况的右半部分都是加一个值，所以第二个树状数组维护最小值。最后 \(1,2\) 情况正着枚举 \(i\)，\(2,4\) 情况倒着枚举 \(i\) 即可。复杂度 \(O(n \log n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
	il int read(){
		int x=0,f=1;char ch=gc;
		while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
		return x*f;
	}
	il int qmi(int a,int b,int p){
		int ans=1;
		while(b){
			if(b&1) ans=ans*a%p;
			a=a*a%p,b>>=1;
		}
		return ans;
	}
	il auto max(auto a,auto b){return (a>b?a:b);}
	il auto min(auto a,auto b){return (a<b?a:b);}
	il int gcd(int a,int b){
		if(!b) return a;
		return gcd(b,a%b);
	}
	il int lcm(int a,int b){
		return a/gcd(a,b)*b;
	}
	il void exgcd(int a,int b,int &x,int &y){
		if(!b) return x=1,y=0,void(0);
		exgcd(b,a%b,x,y);
		int t=x;
		x=y,y=t-a/b*x;
		return ;
	}
	mt19937 rnd(time(0));
}
using namespace yzqwq;

const int N=2e5+10;
int n,p[N],d[N],s[N];
int tr1[N],tr2[N];

il void add1(int x,int y){
	while(x<=n) tr1[x]=max(tr1[x],y),x+=x&(-x);
	return ;
}
int query1(int x){
	int Max=-1e18;
	while(x) Max=max(Max,tr1[x]),x-=x&(-x);
	return Max;
}
il void add2(int x,int y){
	while(x) tr2[x]=min(tr2[x],y),x-=x&(-x);
	return ;
}
int query2(int x){
	int Min=1e18;
	while(x<=n) Min=min(Min,tr2[x]),x+=x&(-x);
	return Min;
}
il void solve(){
	n=rd;
	for(re int i=1;i<=n;++i) p[i]=rd,d[i]=1e18;
	for(re int i=1;i<=n;++i) tr1[i]=-1e18,tr2[i]=1e18;
	for(re int i=1;i<=n;++i){
		d[i]=min(d[i],(p[i]+i)-query1(p[i]));
		add1(p[i],p[i]+i);
		d[i]=min(d[i],-(p[i]-i)+query2(p[i]));
		add2(p[i],p[i]-i);	
	}
	for(re int i=1;i<=n;++i) tr1[i]=-1e18,tr2[i]=1e18;
	for(re int i=n;i>=1;--i){
		d[i]=min(d[i],(p[i]-i)-query1(p[i]));
		add1(p[i],p[i]-i);
		d[i]=min(d[i],-(p[i]+i)+query2(p[i]));
		add2(p[i],p[i]+i);
	}
	for(re int i=1;i<=n;++i) printf("%lld ",d[i]);
	return ;
}

signed main(){
	int t=1;while(t--)
	solve();
	return 0;
}
/*
1. (p[i]+i)-(p[j]+j) p[i]>p[j]^i>j
2. -(p[i]-i)+(p[j]-j) p[i]<p[j]^i>j
3. (p[i]-i)-(p[j]-j) p[i]>p[j]^i<j
4. -(p[i]+i)+(p[j]+j) p[i]<p[j]^i<j
*/