赛后补题两步走

1：赛时脑抽

看到样例6~8：$N<=1e4$，直接就想暴力，结果发现答案太难看了：

先把这一个数列复制两遍，方便与实现左移和右移

答案的移动方式一定是向左走一段后又向右走一段，或者向右走一段后向左走一段，尽量多得在一个方向走到不同的数，但加上另一端要是最优的

把答案拆贡献，正常情况下想的方式是先向左$/$右走一段以后这一段回来会浪费所以乘二，再加上右$/$左边的贡献。(让乘2的那一段少走)

又难看又难算，直接果断放弃！！！

下面给出 题解交给 我赛后的思路......

2：正解推导

我们得到的难看答案一定是要继续拆解的

我们知道当一个点确定时，另一边能满足条件的最优端点也是确定的

那就可以比作每个点上有一个权，你向左向右移动一步都会花费一个代价，因为还要走回来的，最后的答案是走路的代价加上停留的这个点的权

综上，我们先处理掉“点权”，然后依次固定端点，计算最优另一端点和所需代价及贡献(要走的步数)

最后， 不要忘了时间复杂度，看到$N<=5e5$，那计算每一点对应的另一端点时的常规$O(n^2)$的做法就会超时，所以我们用双指针进行优化

当然， 这里还有一个小细节，就是我们这个数列每一个点需要进行的操作最优点可能在这个点的左边$/$右边，所以记得正反都算一边最值。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,bool>mp;
ll a[1000005],f[1000005],t[1000005],sum;
void ins(ll x)
{
    t[x]++;
    if(t[x]==1)sum++;
}//加点权 
void del(ll x)
{
    t[x]--;
    if(!t[x])sum--;
}//减点权 
int main()
{
	memset(f,0x3f,sizeof f);
	ll n;scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),a[i+n]=a[i],mp[a[i]]=1;
    ll flc=mp.size();//集合S中有多少个数 
    for(ll l=1,r=0;l<=n;l++)
	{
        if(l!=1)del(a[l-1]);
		//类似于前缀和(去掉自己前面字母的贡献和代价) 
        while(sum!=flc)ins(a[++r]);
		//找出这个点的最优另一端点 
        f[l]=r-l+1;//两点之间长度 
    }//双指针从左到右算点权 
    memset(t,0,sizeof t);
    sum=0;
    for(ll l=2*n,r=2*n+1;l>n;l--)
	{
        if(l!=n+n)del(a[l+1]);
        while(sum!=flc)ins(a[--r]);
        f[l]=(l-r+1);
    }//从右到左反算一遍 
    for(ll i=1;i<=n;i++)f[i]=min(f[i],f[i+n]);
    for(ll i=1;i<=n;i++)f[i+n]=f[i];
    for(ll i=2;i<=n+n;i++)f[i]=min(f[i-1]+1,f[i]);
    //从左到右算每一个点左边的最优点 
    for(ll i=2*n-1;i>0;i--)f[i]=min(f[i+1]+1,f[i]);
    for(ll i=1;i<=n;i++)f[i]=min(f[i],f[i+n]);
    //从右到左算每一个点右边的最优点，两个点的最优值取最小 
    for(ll i=1;i<=n;i++)printf("%lld ",f[i]-1);
    return 0;
}

AC撒花，题解万岁！！！

介绍一个最好理解最好写的做法！

断环成链，复制两遍。

最后的走路方式一定是向左走一段后又向右走一段，或者向右走一段后向左走一段。

把答案拆贡献，正常情况下想的方式是先向左 / 右走一段以后这一段回来会浪费所以乘二，再加上右 / 左边的贡献。

这样很难做很难看啊！不是吗！

考虑再拆。

考虑到被称作浪费的段可以是从左端回来的路，也可以是从原点过去的路。这是废话，这两段等长。

显然对于固定的左端点其完整覆盖的最优右端点是固定的。

也就是说到了某个点以这个为原始前面的视作浪费，第二部产生的贡献是确定的。

那也就是说每个点上有一个权，你向左向右走一步都会花费一个代价，最后的答案是走路的代价加上停留的这个点的权。最小化答案。

诶这个不就是 AT_abc443_d 吗。银组前一周刚打的还热乎。

做完了，没绷住。

处理点权，我们固定每个左端点，确定最小的右端点，显然可以双指针。

这是向左的，向右其实也同理。

时间复杂度是线性的，于是做完了。

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define mod 998244353
#define int long long
using namespace std;
int a[1000005];
int f[1000005];
int t[1000005];
int sum;
void ins(int x){
    t[x]++;
    if(t[x]==1)sum++;
}
void del(int x){
    t[x]--;
    if(t[x]==0)sum--;
}
void solve(){
    memset(f,0x3f,sizeof f);
    map<int,bool>mp;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i],a[i+n]=a[i],mp[a[i]]=1;
    int flc=mp.size();
    for(int l=1,r=0;l<=n;l++){
        if(l!=1)del(a[l-1]);
        while(sum!=flc)ins(a[++r]);
        f[l]=r-l+1;
    }
    memset(t,0,sizeof t);
    sum=0;
    for(int l=n+n,r=n+n+1;l>n;l--){
        if(l!=n+n)del(a[l+1]);
        while(sum!=flc)ins(a[--r]);
        f[l]=(l-r+1);
    }
    for(int i=1;i<=n;i++)
    f[i]=min(f[i],f[i+n]);
    for(int i=1;i<=n;i++)
    f[i+n]=f[i];
    for(int i=2;i<=n+n;i++)
    f[i]=min(f[i-1]+1,f[i]);
    for(int i=n+n-1;i;i--)
    f[i]=min(f[i+1]+1,f[i]);
    for(int i=1;i<=n;i++)
    f[i]=min(f[i],f[i+n]);
    cout<<f[1]-1;
    for(int i=2;i<=n;i++)
    cout<<' '<<f[i]-1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}
//「……奶油炖肉如何呢？」

//「太棒了！米莉娜最爱吃炖肉了！」

// 她从背后搂住妹妹的肩膀，显得十分高兴。
// 妹妹没有回应。

//「……嗯！好期待喔！」

// 然而，她却满脸欣喜地对妹妹点头。

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
unordered_multiset<int>s;
int a[N],cnt=0,n,count[N];
bool v[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i],a[i+n]=a[i+n*2]=a[i];
			if(!v[a[i]])cnt++,v[a[i]]=true;
	}
	for(int l=1,r=0,cnt=0;l<=n*3;)
	{
		while(r<n*3&&cnt<cnt)
		{
			if(s.find(a[r])==s.end())cnt++;
			s.insert(a[r]);
			r++;	
		}
		count[l]=r-l;
		l++;
	}	
}
//6
//1 2 3 1 3 4 1 2 3 1 3 4 1 2 3 1 3 4
//题意：
//在序列中有个初始位置 i，你可以往左走任意格再往右走，
//要求遍历完所有序列中出现过的数。对于每个 i 都要求出最小步数
//方法： 
//		1：一直往左 
//		2：一直往右 
//		3：先往左再往右
//	 	4：先往右再往左 
//解法： 
//		1：破环成链，复制成3个一样的 
//		2：没遍历完或没有记录全部 
//      3:后面双指针和板子一样，就不写了。。。