题意：

　　给出一个已知的哈希表。求字典序最小的插入序列，哈希表不合法则输出-1。

题解：

　　对于哈希表的每一个不为-1的数，假如他的位置是t，令s = a[t]%n。则这个数可以被插入当且仅当第s ~ t-1个数都不为-1且已经插入完成。

　　那么对于每一个这样的数，需要连t-s条边(s<=t)或者t+n-s条边(s>t)。

　　总的边数有O(n^2)条。可以用线段树优化建图。最后跑一边拓扑排序。

　　对于不合法的情况，第s ~ t-1个数存在-1或者拓扑图存在环会导致不合法。

#include 
      
       using namespace std;#define P pair
       
        const int N = 4e5+10;int t, n;int cnt, tot;int ans[N];int a[N], pre[N];int pos[N], rt[N<<2], deg[N<<2];int head[N<<3], nxt[N<<3], to[N<<3];priority_queue
        
         , greater
         
 > q;void add_edge(int u, int v) {    to[++tot] = v;    nxt[tot] = head[u];    head[u] = tot;    deg[v]++;}void build(int id, int l, int r) {    rt[id] = -1;    if(l == r) {        pos[l] = id;        rt[id] = l;        return;    }    int mid = l+r>>1;    build(id<<1, l, mid);    build(id<<1|1, mid+1, r);    add_edge(id<<1, id);    add_edge(id<<1|1, id);}void update(int id, int l, int r, int ql, int qr, int v) {    if(ql <= l && r <= qr) {        add_edge(id, v);        return ;    }    int mid = l+r>>1;    if(ql <= mid) update(id<<1, l, mid, ql, qr, v);    if(qr > mid) update(id<<1|1, mid+1, r, ql, qr, v);}int main() {    scanf("%d", &t);    while(t--) {        tot = 0;        scanf("%d", &n);        memset(head, -1, sizeof(int)*(n<<3));        memset(deg, 0, sizeof(int)*(n<<2));        for(int i = 0; i < n; i++) {            scanf("%d", &a[i]);            pre[i] = a[i] == -1;            if(i) pre[i] += pre[i-1];        }        int flag = 0;        for(int i = 0; i < n; i++) {            if(~a[i]) {                int s = a[i]%n, t = i;                if(s <= t && pre[t]-(s==0?0:pre[s-1]) || s > t && pre[t]+pre[n-1]-pre[s-1]) {                    flag = 1;                    break;                }            }        }        if(flag) {            puts("-1");            continue;        }        build(1, 0, n-1);        for(int i = 0; i < n; i++) {            if(~a[i]) {                int s = a[i]%n, t = i;                if(s < t) update(1, 0, n-1, s, t-1, pos[t]);                if(s > t) {                    if(t > 0) update(1, 0, n-1, 0, t-1, pos[t]);                    update(1, 0, n-1, s, n-1, pos[t]);                }            }        }        P now;        cnt = 0;        while(!q.empty()) q.pop();        for(int i = 0; i < n; i++) {            if((~a[i]) && deg[pos[i]] == 0) q.push(make_pair(a[i], pos[i]));        }        while(!q.empty()) {            now = q.top();            q.pop();            int u = now.second;            if(~rt[u]) ans[++cnt] = now.first;            for(int i = head[u]; ~i; i = nxt[i]) {                if(--deg[to[i]] == 0) {                    if((~rt[to[i]]) && (~a[rt[to[i]]])) q.push(make_pair(a[rt[to[i]]], to[i]));                    else if(rt[to[i]] == -1) q.push(make_pair(0, to[i]));                }            }        }        if(cnt != n-pre[n-1]) {            puts("-1");            continue;        }        for(int i = 1; i <= cnt; i++) {            printf("%d", ans[i]);            if(i != cnt) printf(" ");        }        puts("");    }}