题解 P6105 【[Ynoi2010]y-fast trie】
RainsAFO
·
·
题解
按照传统先取模，然后分类讨论：
$2.$ $0 \leq (i + j) \leq C - 1$，那么答案在每个 $i$ 最优的 $j$ 取到。
考虑第二种情况。
一个比较 simple 的想法是维护每个 $i$ 的最优匹配 $j$（注意到这是单向的），用 $\text{multiset}$ 维护，但这样删除会被卡到 $O(|S|)$。
对上述做法进行优化，减小可能成为答案的集合。
本题关键在于，如果你要加入/删除一个数 $x1$，其最优匹配为 $x2$ ，需要用这两个数排除掉不优的决策。
这些决策一定至于 $x1,x2$ 相关，设 $x2$ 的最优匹配为 $x3$，若 $x1 > x3$，则 $(x2 , x3)$ 是无用的。
可以证明，保留的匹配个数是 $O(n)$ 级的。
也许会有这样的一个问题，如果删除产生了连锁反应怎么办？
注意到可能的决策集合变化大小始终不超过 $1$ ，而数集是不可重的，也就是说决策集合的元素用到的时候一定对应着数集的变化。
用两个 $\text{multiset}$ 分别维护数集与决策集合，实现有一些细节（注意 $\text{multiset}$ 的 count函数复杂度是错的）。
以下是代码实现，参考了 Owen_codeisking 的代码。
```cpp
#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
register char c = getchar();
register int x = 0, f = 1;
while(c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + c - 48;
c = getchar();
}
return x * f;
}
using namespace std;
int n , C;
multiset <int> s1 , s2;
// s1 : num , s2 : pair
multiset <int> ::iterator it;
inline int get_pair(int x , int o) {
if(x == -1)
return -1;
it = s1.upper_bound(C - x - 1);
if(it == s1.begin())
return -1;
--it;
if(o == 1 && *it == x && s1.count(x) == 1) {
if(it == s1.begin())
return -1;
return *--it;
} else
return *it;
}
int cnt = 0;
inline void insert(int x1) {
cnt++;
if(cnt == 1) {
s1.insert(x1);
return;
}
int x2 = get_pair(x1 , 0);
int x3 = get_pair(x2 , 1);
int x4 = get_pair(x3 , 1);
if(x2 != -1 && x1 > x3) {
if(x3 != -1 && x2 == x4)
s2.erase(s2.find(x2 + x3));
s2.insert(x1 + x2);
}
s1.insert(x1);
}
inline void erase(int x1) {
cnt--;
s1.erase(s1.find(x1));
if(!cnt)
return;int x2 = get_pair(x1 , 0);
int x3 = get_pair(x2 , 1);
int x4 = get_pair(x3 , 1);
if(x2 != -1 && x1 > x3) {
if(x3 != -1 && x2 == x4)
s2.insert(x2 + x3);
s2.erase(s2.find(x1 + x2));
}
}
inline int query(){
it = --s1.end();
int num = *it;
s1.erase(it);
if(s1.find(num) != s1.end()){
s1.insert(num);
return num * 2 % C;
}
// if(s1.count(*it) >= 2)
// return *it * 2 % C;
else{
s1.insert(num);
it = --s1.end();
return (*it + *--it) % C;
}
}
int main() {
n = read() , C = read();
int lstans = 0;
while(n--) {
int opt = read() , x = (read() ^ lstans) % C;
if(opt == 1)
insert(x);
else
erase(x);
if(cnt < 2){
puts("EE");
lstans = 0;
}
else{
lstans = max(query() , s2.empty() ? 0 : *--s2.end());
printf("%d\n" , lstans);
}
}
return 0;
}
```