题解：AT_agc036_b [AGC036B] Do Not Duplicate

· · 题解

看到删除操作就可以往这么一个方向上去想了：

设 nxt_i 代表如果从 i 开始插入，之后环形插入，第一次出现删空之后再往 s 里面加数，加入的第一个数的位置。

（这里的位置可能会 >n，因为我们在记录位置的同时要记录是第几次走到这里，这样才能应对 k 轮的变化）

之后直接暴力跳下一个位置。通过打表可以发现通过跳跃位置作为边建出的图是若干个环，因为每一个点都有正好一个入度、一个出度。

通过周期缩环的方式将 k 次循环操作改为 \le n+1 次操作。因为周期长度必然 \le n+1。紧接着在环上的每一个点暴力跳跃，直到即将超过 n\times k 步。此时还剩下 \le n 步，裸暴力跳跃即可。

时间复杂度为 O(n)，但未完全理解就会觉得它很抽象。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48); 
} 
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
//找从 1 开始的循环节 
const int N=1e6+15;
int n,m,k;
int a[N]; 
int nxt[N];
int nxt_sum[N]; //按数值划分的 nxt  

int lst[N];
int stk[N];
int stk_idx;
#undef int
int main(){
    #define int long long
    n=read(),k=read(),m=n*k;
    for(int i=1;i<=n;i++){
        a[i]=a[i+n]=a[i+2*n]=read();
    }
    //在 long long 范围内 大多数内容都是能够去完成的！ 
    for(int i=3*n;i>=1;i--){
        nxt[i]=nxt_sum[a[i]]+1;
        nxt_sum[a[i]]=i;    //代表未来它会出现的位置 
        //实际上要对环进行各种改造 
    }
//  for(int i=1;i<=n;i++){
//      cout<<nxt[i]<<' ';
//  } 
//  cout<<endl;
    int now=1;
    int circle=0;   //代表一个经过点的环长  
    int circle_=0;  //环长 但是要除以数组长度  
    do{
        circle+=nxt[now]-now;
//      cout<<'$'<<circle<<endl;
        now=nxt[now];
        while(now>n)    now-=n;
//      cout<<'$'<<circle<<' '<<now<<endl; 
    }while(now!=1);
//  return 0;
//  cout<<circle<<endl;
    circle_=circle/n;
//  cout<<'&'<<circle<<' '<<circle_<<endl;
    k%=circle_; //大幅减小环的数目！
//  cout<<'*'<<k<<endl;
    m=n*k;  //距离终点还有最后 m 步！！！！！
    int m1=m;
    now=1;//！！！！！ 
    while(1){
        if(m<nxt[now]-now)  break;  //在这里把它弹出！
        m-=nxt[now]-now;
        now=nxt[now];   //继续跳上去！  
        while(now>n)    now-=n;
//      if(now==1)  break; 
    } 
//  m=m1-m;
//  m1%=m; 
//  return 0;
//  cout<<m<<endl; 
    for(int i=m;i>=1;i--){
        int now=n-i+1;
        now=a[now];
        int lst_=lst[now];
//      cout<<'#'<<now<<' '<<lst_<<endl; 
        if(lst_!=0&&lst_<=stk_idx){
//          cout<<"谭总的世界-017"<<endl; 
            for(int j=lst_;j<=stk_idx;j++){
                lst[stk[j]]=0;
            }
            stk_idx=lst_-1;
        }
        else{
            stk_idx++;
            stk[stk_idx]=now;
            lst[now]=stk_idx;
        }

//      cout<<'^'<<stk_idx<<endl;
//      cout<<endl;
    }
    for(int i=1;i<=stk_idx;i++){
        write1(stk[i]);
    }
    putchar('\n');
    return 0;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！