[DS记录]P6105 [Ynoi2010] y-fast trie
command_block
2021-06-30 16:44:02
**题意** ： 给定一个常数 $C$，你需要维护一个集合 $S$ ，初始时为空。
有 $n$ 次操作：
- 操作1：给出 $x$，插入一个元素 $x$，保证之前集合中没有 $x$ 这个元素
- 操作2：给出 $x$，删除一个元素 $x$，保证之前集合中存在 $x$ 这个元素
每次操作结束后，需要输出从 $S$ 集合中选出两个不同的元素的和 $\bmod\ C$ 的最大值，或指出 $S$ 集合中不足两个元素。
强制在线，$n\leq 5\times 10^5,C,x\leq 2^{63}-1$ ，时限$\texttt{1s}$。
------------
将输入的所有 $x$ 都先模 $C$。
对于和，分 $a+b<C$ 和 $a+b\geq C$ 两类讨论。
对于 $\geq C$ 的情况，只需取 $S$ 中的最大值与次大值进行尝试。
对于 $<C$ 的情况，为每个数 $u$ 找出 $<C-u$ 的最大的 $v$ ，则 $u+v$ 是关于 $u$ 的最佳方案。记为 $u\rightarrow v$ ，称 $u$ 为左端， $v$ 为右端。
考虑动态维护这种匹配。某个左端对应的右端是唯一的，但同一个右端可能对应多个左端，无法保证复杂度。
注意到若 $u_1<u_2$ 且同时有 $u_1,u_2\rightarrow v$ ，则 $u_2\rightarrow v$ 的贡献必定大于 $u_1\rightarrow v$ 的贡献。
于是，对于每个右端，我们只需保留最大的左端。这样化简之后，每个元素相关的匹配数都是 $O(1)$ 的。
又能发现，若 $x$ 作为右端时 $y$ 是最优左端，那么 $y$ 是右端时 $x$ 也是最优左端。这种匹配关系是双向的。
我们猜想修改对这些匹配的影响是 $O(1)$ 的。
插入 $x$ 时，考虑其匹配。
先以 $x$ 作为左端找出右端 $y$ ，再查看 $y$ 原来的匹配 $z$，看看 $x$ 是否 $>z$ ，若是则替代之。
替代后 $z$ 必定无匹配。（ $z$ 的右端是 $y$ ，但 $y$ 不认 $z$ ）
删除 $x$ 时，考虑其匹配。
若没有匹配则直接删除。若匹配 $y$，则将两者同时删除，再加入 $y$ 。
注意可能存在相同的数值。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#include<set>
#define ull unsigned long long
#define Pr pair<ull,int>
#define fir first
#define sec second
#define mp make_pair
#define Itor set<Pr>::iterator
#define ll long long
#define MaxN 500500
using namespace std;
struct Heap{
priority_queue<ull> q0,q1;
void push(ull x){q1.push(x);}
void del(ull x){q0.push(x);}
ull top(){
while(!q0.empty()&&q0.top()==q1.top()){q0.pop();q1.pop();}
return q1.empty() ? 0 : q1.top();
}
}q;
set<Pr> s;
int m,n,tp[MaxN];ull C,w[MaxN];
void insert(int u)
{
Itor it=s.lower_bound(mp(C-w[u],0));
if (it!=s.begin()){
int v=(--it)->sec;
if (!tp[v]){tp[v]=u;tp[u]=v;q.push(w[u]+w[v]);}
else if (w[u]>w[tp[v]]){
int t=tp[v];
tp[t]=0;q.del(w[t]+w[v]);
tp[v]=u;tp[u]=v;q.push(w[u]+w[v]);
}
}s.insert(mp(w[u],u));
}
int main()
{
scanf("%d%llu",&m,&C);
ull las=0;
for (int i=1,op;i<=m;i++){
ull x;
scanf("%d%llu",&op,&x);
x=(x^las)%C;
if (op==1){w[++n]=x;insert(n);}
else {
Itor it=s.lower_bound(mp(x,0));
int u=it->sec;
if (!tp[u])s.erase(it);
else {
int v=tp[u];
tp[u]=tp[v]=0;q.del(w[u]+w[v]);
s.erase(it);s.erase(mp(w[v],v));
insert(v);
}
}
if (s.size()<=1){puts("EE");las=0;}
else {
Itor it=s.end();
ull ans=0;
it--;ans+=it->fir;
it--;ans+=it->fir;
printf("%llu\n",las=max(q.top(),ans%C));
}
}return 0;
}
```