题解 P6105 【[Ynoi2010]y-fast trie】
SymphonyOfEuler
·
·
题解
题意：
维护一个集合，支持集合中一下两种操作：
-
- 插入一个元素（集合中以前没有这个元素的情况下）
-
- 删除一个元素（集合中有这个元素的情况下）
操作完毕后，输出随意两个不同的元素之和的最大值，模 C。若集合长度 < 1，即，不足两个数字，则输出 EE。每次输入需要异或上次的答案。
思路：
考虑用线段树分治。O(nlog^2n)
可惜题目要求强制在线。所以我们换个方法，用 multiset，求解时分两类：
维护 $i$ 的最优匹配 $j$ 时，有一个情况，可以将一些配对忽略。
我们想一下，一个数 $a$，最佳匹配为 $b$，而 $b$ 最佳匹配为 $c$，且 $c$ 大于 $a$，显然，我们要求的尽可能大，可以省去掉前面的那两个数，使用 $b,c$ 这两个。
这样复杂度就从 $O(length(set))$ 优化到了 $O(nlogn)$。
**注意事项：**
- 这题中取 $a$ 的最优匹配的最优匹配的时候，容易把变量搞混，加倍注意。
- 记住，如果输出了 `EE`，一定要把上次答案变量设为 $0$，其他情况也要异或上次答案+设上次答案变量为这次答案。
- `本题读入量约 6 MB，输出量约 5 MB，请选择适合的输入输出方法` lxl的凉心提醒，我选择cin加速，你 自 己 看 着 办。
- 有可能会一片RE，查一下你的函数有没有返回值，$multiset$ 顺序是否正确
**代码：**
```
/* by JS */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
int len, n, c, lans;
multiset<int> mst1, mst2;
struct kafuu_chino {
static inline int ask1(register int d) {
if (d == -1) return -1;
if (mst1.begin() == mst1.upper_bound(c - d - 1)) return -1;
multiset<int>::iterator mst3;
mst3 = mst1.upper_bound(c - d - 1);
--mst3;
if (*mst3 == d && mst1.count(d) == 1) {
if (mst3 == mst1.begin()) return -1;
else return *--mst3;
} else return *mst3;
}
static inline int ask2(register int d) {
if (d == -1) return -1;
if (mst1.begin() == mst1.upper_bound(c - d - 1)) return -1;
multiset<int>::iterator mst3;
mst3 = mst1.upper_bound(c - d - 1);
--mst3;
return *mst3;
}
inline void add(register int d) {
++len;
if (len == 1) {
mst1.insert(d);
return;
}
register int tmp1 = ask2(d), tmp2 = ask1(tmp1), tmp3 = ask1(tmp2);
mst1.insert(d);
if (tmp2 < d && tmp1 != -1) {
if (tmp2 != -1 && tmp1 == tmp3) {
mst2.erase(mst2.find(tmp1 + tmp2));
}
mst2.insert(tmp1 + d);
}
}
inline void del(register int d) {
--len;
_Rb_tree_const_iterator<int> pos = mst1.find(d);
mst1.erase(pos);
if (len == 0) return;
register int tmp1 = ask2(d), tmp2 = ask1(tmp1), tmp3 = ask1(tmp2);
if (tmp2 < d && tmp1 != -1) {
if (tmp2 != -1 && tmp1 == tmp3) {
mst2.insert(tmp1 + tmp2);
}
mst2.erase(mst2.find(tmp1 + d));
}
}
} qwq;
inline void solve() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> c;
for (register int i = 1; i <= n; ++i) {
register int op, x;
cin >> op >> x;
x ^= lans;
if (op == 1) {
x %= c;
qwq.add(x);
}
if (op == 2) {
x %= c;
qwq.del(x);
}
if (len <= 1) {
cout << "EE\n";
lans = 0;
} else {
if (mst2.empty()) {
auto mst3 = --mst1.end();
register int res;
if (mst1.count(*mst3) > 1) {
res = *mst3 * 2 % c;
} else {
res = (*mst3 + *--mst3) % c;
}
cout << max(res, 0) << '\n';
lans = max(res, 0);
} else {
register int query;
auto mst3 = --mst1.end();
if (mst1.count(*mst3) > 1) {
query = *mst3 * 2 % c;
} else {
query = (*mst3 + *--mst3) % c;
}
cout << max(query, *--mst2.end()) << '\n';
lans = max(query, *--mst2.end());
}
}
}
}
int main() {
solve();
return 0;
}
```
**最后：** ~~谔谔我~~