「BZOJ 3578」GTY的人类基因组计划2-Hash

$n$ 个人来做实验,有 $m$ 个房间,一开始所有人都在 $1$ 号房间里,有两个操作:

  1. 让第 $i$ 个人去房间 $j$
  2. 让区间 $[l,r]$ 的房间做实验

实验会获得一些实验信息点数,点数为房间里的人数(不会重复增加点数),求每次操作获得的点数。

链接

BZOJ 3578

题解

可以发现,一次操作最多只能让做实验的房间增加 $2$ 个,所以有用的房间是 $O(q)$ 级别的,我们可以用 set 去维护,每次询问的时候二分(lower_bound)查找就可以了。

现在的关键是如何判断重复,我们可以对每个元素随机一个值,对于集合的 Hash 值,就是其异或和,这样往集合里加一个元素,就是异或它的值,删除一个元素也是异或其值(两次异或就没有了),然后我们把这个 Hash 值放进 Hash 表就可以快速判重了。

最后根据生日悖论,这里的随机值直接 rand 可能要被卡,随机值最好在 long long / unsigned long long 级别。

代码

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
133
134
135
136
137
138
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「BZOJ 3578」GTY的人类基因组计划2 07-10-2017
* Hash
* @author xehoth
*/
#include <bits/stdc++.h>
#include <tr1/unordered_set>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
const int OUT_LEN = 100000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
~InputOutputStream() { flush(); }
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
} io;
}
namespace {
typedef unsigned long long ulong;
inline ulong xorShift128Plus() {
static ulong seed1 = 495;
static ulong seed2 = 233;
register ulong x = seed1;
register const ulong y = seed2;
seed1 = y, x ^= x << 23;
seed2 = x ^ y ^ (x >> 17) ^ (y >> 26);
return seed2 + y;
}
using IO::io;
std::set<int> s;
std::tr1::unordered_set<ulong> exist;
const int MAXN = 100010;
ulong num[MAXN], size[MAXN], pos[MAXN], h[MAXN];
int n, m, q;
inline void solve() {
io >> n >> m >> q;
for (register int i = 1; i <= n; i++) num[i] = xorShift128Plus();
s.insert(1);
for (register int i = 1; i <= n; i++) h[1] ^= num[i], size[1]++, pos[i] = 1;
for (register int i = 1, x, y; i <= q; i++) {
register char c;
io >> c >> x >> y;
switch (c) {
case 'C': {
if (pos[x] == y) continue;
s.erase(pos[x]), s.erase(y);
h[pos[x]] ^= num[x], size[pos[x]]--;
if (exist.find(h[pos[x]]) == exist.end()) s.insert(pos[x]);
h[y] ^= num[x], size[y]++;
if (exist.find(h[y]) == exist.end()) s.insert(y);
pos[x] = y;
break;
}
case 'W': {
register int ans = 0;
for (register std::set<int>::iterator it = s.lower_bound(x);
it != s.end() && *it <= y; it = s.lower_bound(x))
exist.insert(h[*it]), ans += size[*it], s.erase(it);
io << ans << '\n';
break;
}
}
}
}
}
int main() {
#ifdef DBG
freopen("sample/1.in", "r", stdin);
#endif
solve();
return 0;
}
分享到