前言
卡了3天常，总算是压着线卡过去了。。。
对卡常一无所知。
题目
题目链接：https://www.luogu.com.cn/problem/P6105
给定一个常数 \(C\)，你需要维护一个集合 \(S\)，支持 \(n\) 次操作：
- 操作1：给出 \(x\)，插入一个元素 \(x\)，保证之前集合中没有 \(x\) 这个元素
- 操作2：给出 \(x\)，删除一个元素 \(x\)，保证之前集合中存在 \(x\) 这个元素
每次操作结束后，需要输出 \(\max\limits_{\substack{ i, j \in S \\ i \ne j }} \bigl( (i+j) \bmod C \bigr)\)，即从 \(S\) 集合中选出两个不同的元素，其的和 \(\bmod~C\) 的最大值，如果 \(S\) 集合中不足两个元素，则输出 EE。
本题强制在线，每次的 \(x\) 需要 \(\operatorname{xor}\) 上上次答案 ，如果之前没有询问或者输出了 EE，则上次答案为 \(0\)。
思路
我们先将序列中的每一个数都 \(\bmod C\)，那么现在数列中任意两个数 \(a_i+a_j\) 的范围只可能在 \([0,2C)\)。
分成两类处理，第一类是 \(a_i+a_j\in [C,2C)\) 的，第二类是 \(a_i+a_j\in [0,C)\) 的。
对于第一类，很好处理，只要将数列中两个最大的数加起来 \(\bmod C\) 即可。
对于第二类，我们对于数列中的任意一个数 \(a_i\)，我们需要找到数列中另一个数 \(a_j\) 使得 \(a_i+a_j<C\) 且尽量接近 \(C\)。
用平衡树可以轻松的解决这个问题。用 \(\operatorname{set}\) 维护就可以了。
对于插入一个数 \(x\) 的操作，我们在 \(\operatorname{set}\) 中找到第一个小于等于 \(C-x-1\) 的数，将 \(x\) 与这个数匹配，设这个数为 \(y\)。
设 \(pos[x]\) 表示数字 \(x\) 匹配的数，那么如果 \(pos[y]<x\) 的，那么显然将 \(x\) 与 \(y\) 匹配会比 \(y\) 与此时的 \(pos[y]\) 匹配更优，所以将 \(pos[y]\) 改成 \(x\)，同时 \(pos[x]=y\)。
对于删除操作，我们将要删除的数 \(x\) 从 \(\operatorname{set}\) 里面删除，同时将 \(pos[x]\) 也删除，再重新插入 \(pos[x]\) ，让它再次匹配即可。
时间复杂度 \(O(n\log n)\)。
注意 \(pos\) 是需要用 \(\operatorname{map}\) 来记录的。
优化
- 吸氧 + 洛谷自带 O2。
- 用 \(\operatorname{C++11}\) 支持的 \(\operatorname{unordered\_map}\)，各操作时间复杂度为 \(O(1)\)。
- 考虑到如果 \(\operatorname{set}\) 中已经有 \(x\) 这个元素了，再次插入 \(x\) 这个元素是没有必要的。故设 \(cnt[x]\) 表示在 \(\operatorname{set}\) 中数字 \(x\) 出现的次数，那么
- 如果 \(cnt[x]=0\)，直接插入 \(x\)。
- 如果 \(cnt[x]=1\)，在记录答案的容器中插入 \(2x\)。
- 如果 \(cnt[x]>1\)，直接忽略。
- 如果在 \((3)\) 中我们的操作是直接忽略，那么显然答案也是没有变的，直接输出 \(lastans\) 即可。
- 快速读入、快速输出（这个不用说都知道吧）。
- 在 \(\operatorname{set}\) 容器中删除数字 \(x\) 的时候，不要写 \(s.erase(x)\)，写成 \(s.erase(s.find(x))\) ，因为前者的复杂度是 \(O(k+\log n)\) 的，其中 \(k\) 是删除的次数。如果删除多了，时间复杂度就退化至 \(O(n^2)\)。
- 将几个等价的地方时不时改改，说不定就过了（雾）。
- 提交前洗洗脸。
多喝岩浆。
代码
别看了看不懂的。
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <set>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N=500010,Inf=1073741824;
int n,MOD,opt,last,x;
unordered_map<int,int> pos,cnt;
set<int> s;
multiset<int> qans;
multiset<int>::iterator it;
bool qwq,flag;
inline int read()
{
int d=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
return d;
}
inline void write(int x)
{
if (x>9) write(x/10);
putchar(x%10+48);
}
inline void Insert(int x)
{
it=--s.upper_bound(MOD-1-x);
register int p=*it;
if (p==x) p=*--it;
register int posp=pos[p];
if (p>-Inf && x>posp)
{
if (posp>=0)
{
qans.erase(qans.find(p+posp));
pos[posp]=-1;
}
qans.insert(p+x);
pos[p]=x; pos[x]=p;
}
else pos[x]=-1;
if (!qwq) s.insert(x);
}
inline void Delete(int x)
{
int p=pos[x];
pos[x]=-1; s.erase(s.find(x));
if (p<0) return;
qans.erase(qans.find(x+p));
qwq=1; Insert(p); qwq=0;
}
int main()
{
n=read(); MOD=read();
s.insert(-Inf);
while (n--)
{
flag=1;
opt=read(); x=(read()^last)%MOD;
if (opt==1)
{
if (!cnt[x]) Insert(x),flag=0;
if (cnt[x]==1) qans.insert(2*x%MOD),flag=0;
cnt[x]++;
}
else
{
cnt[x]--;
if (!cnt[x]) Delete(x),flag=0;
if (cnt[x]==1) qans.erase(qans.find(2*x%MOD)),flag=0;
}
if (flag)
{
write(last); putchar(10);
continue;
}
int ans=-Inf;
if (s.size()>2) ans=max(ans,(*(--s.end())+*(----s.end()))%MOD);
if (qans.size()) ans=max(ans,*--qans.end());
if (ans>=0) write(last=ans),putchar(10);
else puts("EE"),last=0;
}
}