Hash Function(线段树优化建图+拓扑排序)

描述

传送门:牛客网暑期ACM多校训练营(第四场)- Problem J

Chiaki has just learned hash in today’s lesson. A hash function is any function that can be used to map data of arbitrary size to data of fixed size. As a beginner, Chiaki simply chooses a hash table of size $n$ with hash function $h(x) = x \mod n$.
Unfortunately, the hash function may map two distinct values to the same hash value. For example, when $n = 9$ we have $h(7) = h(16) = 7$. It will cause a failure in the procession of insertion. In this case, Chiaki will check whether the next position is available or not. This task will not be finished until an available position is found. If we insert $\lbrace 7, 8, 16 \rbrace$ into a hash table of size $9$, we will finally get $ \lbrace 16, -1, -1, -1, -1, -1, -1, 7, 8 \rbrace$. Available positions are marked as $-1$.
After done all the exercises, Chiaki became curious to the inverse problem. Can we rebuild the insertion sequence from a hash table? If there are multiple available insertion sequences, Chiaki would like to find the smallest one under lexicographical order.
Sequence $a_1, a_2, …, a_n$ is lexicographically smaller than sequence $b_1, b_2, …, b_n$ if and only if there exists $i$ ($1 ≤ i ≤ n$) satisfy that $a_i < b_i$ and $a_j = b_j$ for all $1 ≤ j < i$.

输入描述

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line of each case contains a positive integer $n$ ($1 ≤ n ≤ 2 \times 10^5$) – the length of the hash table.
The second line contains exactly $n$ integers $a_1,a_2,…,a_n$ ($-1 ≤ a_i ≤ 10^9$).
It is guaranteed that the sum of all $n$ does not exceed $2 \times 10^6$.

输出描述

For each case, please output smallest available insertion sequence in a single line. Print an empty line when the available insertion sequence is empty. If there’s no such available insertion sequence, just output $-1$ in a single line.

示例

输入

1
2
3
4
5
6
7
3
9
16 -1 -1 -1 -1 -1 -1 7 8
4
8 5 2 3
10
8 10 -1 -1 34 75 86 55 88 18

输出

1
2
3
7 8 16
2 3 5 8
34 75 86 55 88 18 8 10

思路

  • 当$x$插入到$j$而应该插入到$i = x \pmod n$时,如果$[i, j)$中间有$-1$,则序列不合法。
  • 然后我们可以从Hash表中得出的信息就是一个区间里的数要比一个数插入得早。
  • 使用数据结构(线段树)优化建图后拓扑排序即可。
  • 注意特判空序列的时候要输出一个空行。否则会格式错误(明明就是WA了)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 18;
typedef pair<int, int> PII;
int a[N], fix[N];
int id[N << 2], pos[N << 2];
int n;
vector<int> G[N << 2];
int deg[N << 2];

inline void init(int n)
{
memset(deg, 0, sizeof(int) * (n << 2 | 5));
for (int i = 0; i < (n << 2 | 5); i++) G[i].clear();
}

inline void addedge(int u, int v)
{
G[u].push_back(v);
++deg[v];
}

#define lson o << 1
#define rson o << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson
void build(int l = 0, int r = n - 1, int o = 1)
{
id[o] = -1;
if (l == r)
{
pos[l] = o, id[o] = l;
return;
}
int m = l + r >> 1;
addedge(lson, o);
addedge(rson, o);
build(Lson);
build(Rson);
}

void Addedge(int L, int R, int p, int l = 0, int r = n - 1, int o = 1)
{
// cerr << "[" << L << ", " << R << "]" << id[p] << endl;
if (L <= l && r <= R)
{
addedge(o, p);
return;
}
int m = l + r >> 1;
if (L <= m) Addedge(L, R, p, Lson);
if (m < R) Addedge(L, R, p, Rson);
}

inline bool judge(int s, int t)
{
if (s <= t) return (fix[t] - fix[s] == 0) && ~a[s];
return !fix[t] && fix[n - 1] - fix[s - 1] == 0;
}

inline void topo()
{
priority_queue<PII, vector<PII>, greater<PII>> q;
for (int i = 0; i < n; i++)
if (!deg[pos[i]]) q.push({a[i], pos[i]});
vector<int> ans;
while (!q.empty())
{
PII cur = q.top();
q.pop();
int u = cur.second;
if (~cur.first) ans.push_back(cur.first);
for (auto& v : G[u])
if (--deg[v] == 0) q.push({~id[v] ? a[id[v]] : -1, v});
}
int m = ans.size();
if (m != n - fix[n - 1])
{
puts("-1");
return;
}
if (m == 0)
{
puts("");
return;
}
for (int i = 0; i < m; i++) printf("%d%c", ans[i], " \n"[i == m - 1]);
}

inline void solve()
{
scanf("%d", &n);
init(n);
for (int i = 0; i < n; i++)
{
scanf("%d", a + i);
if (i)
fix[i] = fix[i - 1] + (a[i] == -1);
else
fix[i] = (a[i] == -1);
}

for (int i = 0; i < n; i++)
if (~a[i] && !judge(a[i] % n, i))
{
puts("-1");
return;
}
build();
for (int i = 0; i < n; i++)
if (~a[i])
{
int s = a[i] % n, t = i;
if (s == t) continue;
if (s < t)
Addedge(s, t - 1, pos[i]);
else
{
if (t) Addedge(0, t - 1, pos[i]);
Addedge(s, n - 1, pos[i]);
}
}
topo();
}

int main()
{
int T;
scanf("%d", &T);
while (T--) solve();
}
捐助作者
0%