记录一下学到的新姿势：线段树优化建图

题目大意：
已知哈希函数为 hash(x) = x mod n ，且如果出现哈希冲突，则 hash(x) = hash(x+1)。
现给出一张 hash 表，长度为 n，问字典序最小插入顺序。

知识点： 线段树优化建图、拓扑排序

解题思路：

对于一个数 x，设它所在的位置为 pos，如果 pos ≠ x%n，则 pos 左边，x%n 及其右边所有的数都要在 x 之前插入（如果这个区间里面有 -1，那么输出 "-1" ），所以我们可以从这个区间中的所有点连一条边到 x，跑完拓扑排序即可得到答案（如果图有环也输出 "-1" ）。但是，普通的建图方式是 O(n2)，这显然不够优秀，题解跟我们介绍了一种用线段树优化的建图方法：建一棵线段树，将哈希表中所有的数作为叶子结点，从所有的子结点往父节点连一条边。若要将一个区间中的数连到 x ，只需将这个区间对应的所有父结点连到 x 即可，复杂度 O(log n)。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
const int INF=0x3f3f3f3f;
const int MAXN=2e5+5;
vector G[MAXN*6];
struct Point{
    int du,num,id;
    friend bool operator <(const Point a,const Point b){
        return a.num>b.num;
    }
}pt[MAXN*6];
int a[MAXN];
bool flag[MAXN<<2];
int tree[MAXN<<2],ind;
void pushup(int rt){
    G[tree[rt<<1]].push_back(tree[rt]);
    G[tree[rt<<1|1]].push_back(tree[rt]);
    pt[tree[rt]].du+=2;
    flag[rt]=flag[rt<<1]||flag[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        tree[rt]=l;
        G[tree[rt]].clear();
        pt[tree[rt]].du=0;
        pt[tree[rt]].num=a[l];
        pt[tree[rt]].id=l;
        if(a[l]<0)  flag[rt]=true;
        else    flag[rt]=false;
        return;
    }
    tree[rt]=ind++;
    G[tree[rt]].clear();
    pt[tree[rt]].du=0;
    pt[tree[rt]].num=-2;
    pt[tree[rt]].id=tree[rt];
    int m=(l+r)/2;
    build(lson);
    build(rson);
    pushup(rt);
}
bool add(int L,int R,int to,int l,int r,int rt){
    if(L<=l&&r<=R){
        G[tree[rt]].push_back(to);
        pt[to].du++;
        return flag[rt];
    }
    int m=(l+r)/2;
    bool ret=false;
    if(L<=m)    ret=ret||add(L,R,to,lson);
    if(m<R)     ret=ret||add(L,R,to,rson);
    return ret;
}
priority_queue que;
int ans[MAXN];
int main(){
    int mod,T;
    scanf("%d",&T);
    while(T--){
        while(!que.empty()) que.pop();
        scanf("%d",&mod);
        int have=0;
        for(int i=0;i<mod;i++){
            scanf("%d",&a[i]);
            if(a[i]>=0) have++;
        }
        ind=mod;
        build(0,mod-1,1);
        bool temp=false;
        for(int i=0;i<mod;i++){
            if(a[i]>=0){
                int pos=a[i]%mod;
                if(pos<i)
                    temp=add(pos,i-1,i,0,mod-1,1);
                else if(pos>i){
                    if(i>0)
                        temp=temp||add(0,i-1,i,0,mod-1,1);
                    temp=temp||add(pos,mod-1,i,0,mod-1,1);
                }
                if(temp){
                    puts("-1");
                    break;
                }
            }
        }
        if(temp)    continue;
        for(int i=0;i<ind;i++){
            if(pt[i].du==0)
                que.push(pt[i]);
        }
        Point now;
        int cnt=0;
        while(!que.empty()){
            now=que.top();
            que.pop();
            if(now.num<0){
                for(int i=0;i<G[now.id].size();i++){
                    int v=G[now.id][i];
                    pt[v].du--;
                    if(pt[v].du==0) que.push(pt[v]);
                }
            }
            else{
                ans[cnt++]=now.num;
                for(int i=0;i<G[now.id].size();i++){
                    int v=G[now.id][i];
                    pt[v].du--;
                    if(pt[v].du==0) que.push(pt[v]);
                }
            }
        }
        if(cnt<have)
            puts("-1");
        else if(cnt==0)
            puts("");
        else{
            printf("%d",ans[0]);
            for(int i=1;i<cnt;i++){
                printf(" %d",ans[i]);
            }puts("");
        }
    }
    return 0;
}