Tokitsukaze and Hash Table

线段树上二分即可

没错我来误导大家了

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){if(chr=='-')f=-1;chr=getchar();}
    while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans*f;
}const int M = 1e6+5;
int s[M<<2],n,a[M],t[M<<2],ans[M];
#define ls (i<<1)
#define rs (i<<1|1)
#define mid (l+r>>1)
inline void Push_Up(int i){s[i]=s[ls]+s[rs];}
void Update(int i,int l,int r,int x,int sum){
    if(l==r){++s[i],t[i]=sum;return;}
    if(x<=mid) Update(ls,l,mid,x,sum);
    else Update(rs,mid+1,r,x,sum);
    Push_Up(i);
}
int query(int i,int l,int r,int x){
    if(l==r) return t[i];
    Push_Up(i);
    if(x<=mid) return query(ls,l,mid,x);
    return query(rs,mid+1,r,x);
}
int Query_Try(int i,int l,int r,int ql,int qr){
    if(l==r){if(!s[i]) return l;return n+1;}
    if(ql<=l&&r<=qr){
        if((mid-l+1)-s[ls]!=0)return Query_Try(ls,l,mid,ql,qr);
        return Query_Try(rs,mid+1,r,ql,qr);
    }int ans=0;
    if(ql<=mid&&mid-l+1-s[ls]!=0)ans=Query_Try(ls,l,mid,ql,qr);
    if(ans<ql||ans>qr)return Query_Try(rs,mid+1,r,ql,qr);
    return ans;
}
int main(){
    n=read();
    for(register int i=1;i<=n;++i){
        int x=read();
        register int l=x%n+1,r=n,pos=n+1;
        pos=Query_Try(1,1,n,l,r);
        if(pos==n+1)pos=Query_Try(1,1,n,1,l-1);
        Update(1,1,n,pos,x);
    }for(int i=1;i<=n;i++)printf("%d ",query(1,1,n,i));
    return 0;
}