破环成链 破成$3n$大小的链

首先考虑$O(n^2)$做法

枚举每一个$x$

然后枚举所有区间的左端点$l$ 双指针找到满足条件的最靠左的右端点$r$

若$x$在$[l,r]$内 那么指针选择该区间步数为 $min(x-l,r-x)+r-l$

否则 步数为$x$到$[l,r]$的距离加上区间的长度

现在考虑能否同时处理所有的点

对于每一个合法区间 根据以上步数计算方法 可以分成四段:

$1.[1,l-1]: -x+r$

$2.[l,r]:$

$a.x<(l+r)/2:x+r-2*l$

$b.x>=(l+r)/2:-x+2*r-l$

$3.[r+1,3n]:x-l$

于是我们用两颗线段树维护一下$x$后面的东西 统计答案再加或减$x$即可

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define F first
#define S second
#define mkp make_pair
#define bug cout<<"---\n";
#define pii pair<int,int>
#define ls(p) (p<<1)
#define rs(p) ((p<<1)|1)
#define ppb pop_back
#define ppf pop_front
#define psb push_back
const int inf=1e9+1,mod=1e9+7;
int n,a[1501000];
struct SegMent_Tree{
	struct Tree{
		int tl,tr,dat,add;
	}tree[2010000];
	void build(int p,int l,int r){
		tree[p]={l,r,inf,inf};
		if(l==r) return ;
		int mid=((l+r)>>1);
		build(ls(p),l,mid);
		build(rs(p),mid+1,r);
	} 
	void down(int p){
		int z=tree[p].add;
		tree[p].add=inf;
		if(z!=inf){
			tree[ls(p)].dat=min(tree[ls(p)].dat,z);
			tree[rs(p)].dat=min(tree[rs(p)].dat,z);
			tree[ls(p)].add=min(tree[ls(p)].add,z);
			tree[rs(p)].add=min(tree[rs(p)].add,z);
		}
	}
	void update(int p,int l,int r,int val){
		
		if(l>r) return ;
		int nl=tree[p].tl,nr=tree[p].tr;
		if(l<=nl&&r>=nr){
			tree[p].dat=min(tree[p].dat,val);
			tree[p].add=min(tree[p].add,val);
			return ;
		}down(p);
		int mid=((nl+nr)>>1);
		if(l<=mid) update(ls(p),l,r,val);
		if(r>mid) update(rs(p),l,r,val);
	}
	int ask(int p,int w){
		int nl=tree[p].tl,nr=tree[p].tr;
		if(nl==nr){
			return tree[p].dat;
		}down(p);
		int mid=((nl+nr)>>1);
		if(w<=mid) return ask(ls(p),w);
		else return ask(rs(p),w);
	}
}smtl,smtr;
int vis[501000],cnt[501000],scnt,ok;
void pls(int x){
	cnt[a[x]]++;
	if(cnt[a[x]]==1) ok++;
}
void del(int x){
	cnt[a[x]]--;
	if(cnt[a[x]]==0) ok--;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	smtl.build(1,n+1,n+n);
	smtr.build(1,n+1,n+n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(vis[a[i]]==0) scnt++;
		vis[a[i]]=1;
		a[i+n]=a[i+2*n]=a[i];
	}
	int r=0;
	for(int l=1;l<=3*n;l++){
		while(ok<scnt&&r<=3*n) pls(++r);
		if(ok<scnt) break;
		int mid=((l+r)>>1);
		smtl.update(1,max(n+1,r+1),n+n,-l);
		smtl.update(1,max(n+1,l),min(n+n,mid),r-2*l);
		smtr.update(1,n+1,min(n+n,l-1),r);
		smtr.update(1,max(n+1,mid+1),min(n+n,r),2*r-l);
		del(l);
	}
	for(int i=n+1;i<=n+n;i++){
		cout<<min(smtl.ask(1,i)+i,smtr.ask(1,i)-i)<<" ";
	}
	return 0;
}