题解 P6105 [Ynoi2010] y-fast trie
Terac
·
·
题解
\texttt{link}
题意
给定常数 C，维护一个集合 S，n 次操作，支持插入、删除，每次操作后询问 \max\limits_{i,j\in S\land i\ne j}\{(i+j)\bmod C\}，强制在线。
数据范围：1\le n\le 5\times 10^5,1\le C\le 1073741823
题解
以下默认 |S|,n 同级。
首先发现加入一个数的时先对它取模不影响正确性，也便于处理。
然后思考下这个模 C 意义下和的最大值。
发现可以分类讨论：
- 当 C\le i+j\le 2\times C 时，从集合中取最大值和次大值出来即可。
- 当 0\le i+j < C 时，可以想到个暴力，对于每个 x\in S，找到 \max\limits_{y\in S\land x\ne y}((x+y)\bmod C)，在这些值中取最大值即可。
第一类情况 simple，我们只看第二类。
在这个过程中有许多的匹配是不优的，但我们都考虑了进去，每次插入删除要更新的个数级别是 $O(n)$ 的，考虑维护更少的匹配。
有个结论，若 $x$ 的最优匹配是 $y$，$y$ 的最优匹配是 $z$，那么 $(x+y)\bmod C$ 不如 $(y+z)\bmod C$。
这个结论证明也很显然，存在这种情况说明 $y$ 有更好的选择。这个结论可推出只用维护所有双向的匹配即可，每次插入删除要更新的数就变成 $O(1)$ 的了。
于是每次插入 $x$ 考虑其最优匹配 $y$，看 $x$ 是否能对 $y$ 的匹配产生影响，删除相当于重新插入 $y$，这样的复杂度就是 $O(n\log n)$ 的。
因为插入集合后对 $C$ 取模了，所以可能会有重复，用 STL 的 `multiset` 就好，注意找匹配时可能会找回自己，要判掉。
```cpp
#include <bits/stdc++.h>
#define IT multiset<int>::iterator
using namespace std;
multiset<int> s, pr;
int n, c;
int mat(int x, bool t) {
if(!~x) return -1;
IT it = s.upper_bound(c - 1 - x);
if(it == s.begin()) return -1;
--it;
if(t && *it == x && s.count(x) == 1)
return it == s.begin() ? -1 : *--it;
return *it;
}
void ins(int x) {
if(s.empty()) { s.insert(x); return; }
int y = mat(x, 0), z = mat(y, 1), w = mat(z, 1);
if(~y && x > z) {
if(~z && y == w) pr.erase(pr.find(y + z));
pr.insert(x + y);
}
s.insert(x);
}
void del(int x) {
s.erase(s.find(x));
if(s.empty()) return;
int y = mat(x, 0), z = mat(y, 1), w = mat(z, 1);
if(~y && x > z) {
if(~z && y == w) pr.insert(y + z);
pr.erase(pr.find(x + y));
}
}
int qry() {
int res;
IT it = --s.end();
if(s.count(*it) >= 2) res = *it * 2 % c;
else res = (*it + *--it) % c;
if(!pr.empty()) res = max(*--pr.end(), res);
return res;
}
int main() {
scanf("%d%d", &n, &c);
int opt, x, last = 0;
while(n--) {
scanf("%d%d", &opt, &x);
x = (x ^ last) % c;
if(opt == 1) ins(x);
else del(x);
if(s.size() < 2) puts("EE"), last = 0;
else printf("%d\n", last = qry());
}
return 0;
}
```