2018牛客多校第四场 J.Hash Function

题意：

　　给出一个已知的哈希表。求字典序最小的插入序列，哈希表不合法则输出-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 <bits/stdc++.h>

using namespace std;

#define P pair<int, int>

const int N = 4e5+;

int t, n;

int cnt, tot;

int ans[N];

int a[N], pre[N];

int pos[N], rt[N<<], deg[N<<];

int head[N<<], nxt[N<<], to[N<<];

priority_queue<P, vector<P>, greater<P> > 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] = -;

    if(l == r) {

        pos[l] = id;

        rt[id] = l;

        return;

    }

    int mid = l+r>>;

    build(id<<, l, mid);

    build(id<<|, mid+, r);

    add_edge(id<<, id);

    add_edge(id<<|, 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>>;

    if(ql <= mid) update(id<<, l, mid, ql, qr, v);

    if(qr > mid) update(id<<|, mid+, r, ql, qr, v);

}

int main() {

    scanf("%d", &t);

    while(t--) {

        tot = ;

        scanf("%d", &n);

        memset(head, -, sizeof(int)*(n<<));

        memset(deg, , sizeof(int)*(n<<));

        for(int i = ; i < n; i++) {

            scanf("%d", &a[i]);

            pre[i] = a[i] == -;

            if(i) pre[i] += pre[i-];

        }

        int flag = ;

        for(int i = ; i < n; i++) {

            if(~a[i]) {

                int s = a[i]%n, t = i;

                if(s <= t && pre[t]-(s==?:pre[s-]) || s > t && pre[t]+pre[n-]-pre[s-]) {

                    flag = ;

                    break;

                }

            }

        }

        if(flag) {

            puts("-1");

            continue;

        }

        build(, , n-);

        for(int i = ; i < n; i++) {

            if(~a[i]) {

                int s = a[i]%n, t = i;

                if(s < t) update(, , n-, s, t-, pos[t]);

                if(s > t) {

                    if(t > ) update(, , n-, , t-, pos[t]);

                    update(, , n-, s, n-, pos[t]);

                }

            }

        }

        P now;

        cnt = ;

        while(!q.empty()) q.pop();

        for(int i = ; i < n; i++) {

            if((~a[i]) && deg[pos[i]] == ) 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]] == ) {

                    if((~rt[to[i]]) && (~a[rt[to[i]]])) q.push(make_pair(a[rt[to[i]]], to[i]));

                    else if(rt[to[i]] == -) q.push(make_pair(, to[i]));

                }

            }

        }

        if(cnt != n-pre[n-]) {

            puts("-1");

            continue;

        }

        for(int i = ; i <= cnt; i++) {

            printf("%d", ans[i]);

            if(i != cnt) printf(" ");

        }

        puts("");

    }

}