题目链接：CCPC-Wannafly 2018WC Day7 E.线性探测法

题意：

给一个长度为n的数组b[i]，表示经过hash之后的数组，求原数组的最小字典序。

题解：

如果b[i]%n=i，表示刚好在原位，即没有产生冲突。所以当b[i]%n!=i时，则区间[b[i]%n,i-1]中所有的数都在b[i]之前，由该区间向该点建边，然后拓扑排序即可。

小数据可以暴力建图，大数据需要线段树优化建图。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+9;
const int MAXM=1e3+9;
const int inf=1e3+9;
int n;
int deg[MAXN<<3],pos[MAXN<<3],id[MAXN<<3],b[MAXN];
struct Edge
{
    int v,nxt;
} edge[MAXN<<3];
int fir[MAXN<<3],cnt=0;
void addedge(int u,int v)
{
    edge[cnt].v=v;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
    deg[v]++;
}
void build(int l,int r,int rt)
{
    id[rt]=-1;
    if(l==r)
    {
        pos[l]=rt;
        id[rt]=l;
        return;
    }
    addedge(rt<<1,rt);
    addedge(rt<<1|1,rt);
    int mid=(l+r)/2;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
void ADDEDGE(int L,int R,int p,int l,int r,int rt,bool flag)
{
    if(L<=l&&r<=R)
    {
        if(flag)
            addedge(rt,p);
        else
            addedge(p,rt);
        return;
    }
    int mid=(l+r)/2;
    if(L<=mid)
        ADDEDGE(L,R,p,l,mid,rt<<1,flag);
    if(R>mid)
        ADDEDGE(L,R,p,mid+1,r,rt<<1|1,flag);
}
void topo()
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
    while(!que.empty())
        que.pop();
    for(int i=0; i<n; i++)
        if(!deg[pos[i]])
            que.push({b[i],pos[i]});
    vector<int> ans;
    ans.clear();
    while(!que.empty())
    {
        pair<int,int>   p=que.top();
        que.pop();
        int u=p.second;
        if(p.first!=-1)
            ans.push_back(p.first);
        for(int i=fir[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            if(--deg[v]==0)
            {
                if(id[v]==-1)
                    que.push({-1,v});
                else
                    que.push({b[id[v]],v});
            }
        }
    }
    for(int i=0; i<ans.size(); i++)
        if(i==0)
            printf("%d",ans[i]);
        else
            printf(" %d",ans[i]);
}
int main()
{
    scanf("%d",&n);
    memset(fir,-1,sizeof(fir));
    memset(deg,0,sizeof(deg));
    for(int i=0; i<n; i++)
        scanf("%d",&b[i]);
    build(0,n-1,1);
    for(int i=0; i<n; i++)
    {
        int s=b[i]%n,t=i;
        if(s==t)
            continue;
        if(s<t)
            ADDEDGE(s,t-1,pos[i],0,n-1,1,1);
        else
        {
            if(t)
                ADDEDGE(0,t-1,pos[i],0,n-1,1,1);
            ADDEDGE(s,n-1,pos[i],0,n-1,1,1);
        }
    }
    topo();
    return 0;
}