题目描述
https://codeforces.com/contest/1732/problem/D2
简要题意：现在你有一个集合 $S$，$S$ 中只有一个元素 $0$，同时有 $q$ 次操作，操作有三种，第一种操作向集合中加入一个数 $x$；第二种操作从集合中删掉数 $x$；第三种操作给定 $k$，询问集合的 $k-mex$，$k-mex$ 表示最小的数 $x$，满足 $x$ 是 $k$ 的倍数，且在 $S$ 中不存在
$q\le 2\times 10^5,x,k\le 10^{18}$
Solution
我们首先考虑不存在删除操作如何做，容易发现我们对于每个 $k$ 维护答案即可，即我们记录最大的 $x$，满足 $0,k,\cdots,x-k$ 都存在且 $x$ 不存在，这个东西的具体操作就是在每次询问的时候暴力检查，注意到链的总长度大概是 $O(n\log )$ 的级别
然后我们考虑删除，对于每个 $k$ 我们依然记录最大的 $x$，不过我们记录的 $x$ 是历史最大，同时我们考虑对于每个 $k$ 记录 $k$ 到 $x$ 之间后来被删掉的数 $y$，这样我们每次询问的时候暴力判断每个被记录的 $y$ 是否被重新加入，如果全部被重新加入则从 $x$ 开始再次暴力判断
那么我们考虑当我们删掉一个数 $x$，我们如何找到 $x$ 作为 $y$ 的所有 $k$，这个东西其实非常简单，我们对于每个数 $x$ 开一个 $set$ 记录数 $x$ 所在的所有链的链尾，这样如果我们删掉 $x$，就在它所在的所有链尾将其作为 $y$ 加入，对于这个 $set$ 的维护，我们在询问暴力的时候维护即可
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
| #include <iostream>
#include <map>
#include <set>
#define maxn 200010
#define ll long long
using namespace std;
int q;
map<ll, ll> ans;
map<ll, set<ll>> S, T;
set<ll> ext;
inline void solve_1() {
ll x; cin >> x;
ext.insert(x);
}
inline void solve_2() {
ll x; cin >> x;
ext.erase(x);
for (auto y : S[x])
T[y].insert(x / y);
S[x].clear();
}
inline void solve_3() {
ll x; cin >> x;
if (!ans.count(x)) ans[x] = 1;
ll k = ans[x];
while (T[x].size()) {
ll k = *T[x].begin();
if (ext.count(k * x)) T[x].erase(k), S[k * x].insert(x);
else break;
}
if (T[x].size()) return cout << *T[x].begin() * x << "\n", void();
while (ext.count(k * x)) S[k * x].insert(x), ++k;
ans[x] = k; cout << k * x << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> q;
while (q--) {
char c[10]; cin >> c;
if (c[0] == '+') solve_1();
else if (c[0] == '-') solve_2();
else solve_3();
}
return 0;
}
|