【Ynoi2010】y-fast trie
STL，平衡树。
题目大意：
给定一个集合和一个正整数 $C$，支持两个操作。
- 插入一个元素 $x$，保证 $x$ 原来不存在。
- 删除一个元素 $x$，保证 $x$ 原来存在。
每次操作完后，要求在集合中选出两个不同元素 $A,B$，使得 $(A+B)\bmod C$ 的值最大。输出最大值。
题解：
我们可以对 $x$ 进行取模，这样显然不会影响答案，但是会出现重复的情况。
假设我们选出的 $A\geq B$。
我们进行分类讨论：
$A+B\geq C$，此时我们要最大化 $A+B-C$ 的值，显然选最大的两个最优。使用优先队列完成。
$A+B\lt C$，且 $A\lt\lceil\frac C 2\rceil$。此时由于 $B\leq A$，所以无论如何选 $B$ 都不会达到 $C$。这种情况，我们只需要选两个小于 $\lceil\frac C 2\rceil$ 即可。也使用优先队列完成。
$A+B\lt C$，且 $A\geq \lceil\frac C 2\rceil$。考虑对于一个 $A$，能够和它加起来不需要取模的数的范围为 $[0,C-1-A]$。不难发现，$A$ 越大，区间越小，且能产生的贡献都是一段前缀。
我们显然要求贡献最大，所以每个 $A$ 所覆盖到的是一段连续的区间，这段区间里的数作为 $B$ 时，和当前的 $A$ 加起来取得最大贡献。
新加一个数相当于插入一个区间，删除一个数相当于把一个区间和后面一个并起来。
而且这些区间从左到右贡献递减。所以加入、删除一段区间可以看做一个区间加的操作。而我们要求的是全局最大值。
由于可能作为 $B$ 的值只有 $n$ 个，所以可以使用动态开点线段树实现区间加、全局最大值。
但由于本题要求线性空间，所以需要使用平衡树来代替线段树。
单次修改的复杂度显然是 $O(\log n)$。
这里所有操作都是单次 $O(\log n)$。
总时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。
代码上，没有纯 STL 的做法好写。但是思路非常简单。
大概用棵 ODT 代替平衡树就可以纯 STL？
fhq treap 常数有点大，略卡常。
Update(2020.10.15):手写哈希表把 unordered_map 吊起来锤。
Code：
#include<set>
#include<random>
#include<algorithm>
#include<cstdio>
#include<cctype>
#include<ctime>
#include<queue>
using namespace std;
char buf[(int)1e7],*ss=buf;
inline int init(){buf[fread(buf,1,(int)1e7-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline int readint(){
int d=0;
while(!isdigit(*ss))++ss;
while(isdigit(*ss))d=d*10+(*ss++^'0');
return d;
}
char bwf[9000005],*ww=bwf;
int xx[12];
inline void print(int x){
static int*q=xx;
if(!x)*ww++='0';else{
for(;x;x/=10)*q++=(x%10)^'0';
while(q!=xx)*ww++=*--q;
}
*ww++='\n';
}
mt19937 mt(time(0));
struct Hash_Table{
static const int M=4565473,md=M-2;
int cnt[M],head[M],nxt[M],tot;
int val[M];
Hash_Table(){tot=0;}
inline int&operator[](const int&k){
const int x=k%md;
for(int i=head[x];i;i=nxt[i])
if(val[i]==k)return cnt[i];
nxt[++tot]=head[x],head[x]=tot,val[tot]=k;
return cnt[tot];
}
}mp;
set<int>_1;
const int N=5e5+6;
int n,md,t0t,last;
struct DS{
priority_queue<int>p,q;
int sz;
inline void insert(int x){p.push(x),++sz;}
inline void erase(int x){q.push(x),--sz;}
inline int ask(){
if(sz<2)return 0;
while(!q.empty()&&p.top()==q.top())p.pop(),q.pop();
int u=p.top();p.pop();
while(!q.empty()&&p.top()==q.top())p.pop(),q.pop();
int v=p.top();p.push(u);
return u+v<md?u+v:u+v-md;
}
}_2,big;
namespace sbt{
struct node{
int val,mx,ls,rs,sz,tag,pos;
unsigned ran;
}d[N];
int rt,nod;
inline void add(int x,int v){d[x].val+=v,d[x].mx+=v,d[x].tag+=v;}
inline void update(int x){
const int ls=d[x].ls,rs=d[x].rs;
d[x].mx=max({d[ls].mx,d[rs].mx,d[x].val});
d[x].sz=d[ls].sz+d[rs].sz+1;
}
inline void pushdown(int x){
if(int&q=d[x].tag){
const int ls=d[x].ls,rs=d[x].rs;
if(ls)add(ls,q);
if(rs)add(rs,q);
q=0;
}
}
int merge(int x,int y){
if(!x||!y)return x|y;
pushdown(x),pushdown(y);
if(d[x].ran<d[y].ran)
{d[x].rs=merge(d[x].rs,y),update(x);return x;}
d[y].ls=merge(x,d[y].ls),update(y);return y;
}
void split(int u,int k,int&x,int&y){
if(!u)x=y=0;else
if(d[pushdown(u),u].pos<=k)split(d[u].rs,k,d[u].rs,y),x=u,update(x);else
split(d[u].ls,k,x,d[u].ls),y=u,update(y);
}
void modify(int l,int r,int v){
int x,y,z;
split(rt,l-1,x,y);
split(y,r,y,z);
if(y)add(y,v);
rt=merge(merge(x,y),z);
}
void insert(int pos,int v){
d[++nod]=(node){v,v,0,0,1,0,pos,mt()};
int x,y;
split(rt,pos,x,y);
rt=merge(merge(x,nod),y);
}
void erase(int pos){
int x,y,z;
split(rt,pos-1,x,y);
split(y,pos,y,z);
rt=merge(x,z);
}
}
int main(){
sbt::d[0].mx=sbt::d[0].val=-2e9;
n=readint(),md=readint();
_1.insert(-md-1),_1.insert(md);
while(n--){
int op=readint(),x=(readint()^last)%md;
if(op==1){
++t0t;
big.insert(x);
if(!mp[x]){
if(x>=(md+1)/2){
auto it=_1.upper_bound(x);
int l=md-*it,r=md-1-x;
sbt::modify(l,r,x-*--it);
_1.insert(x);
}else _2.insert(x);
int pr=*--_1.upper_bound(md-1-x);
sbt::insert(x,x+pr);
mp[x]=1;
}else{
++mp[x];
if(x<(md+1)/2)_2.insert(x);
}
}else{
--t0t;
big.erase(x);
if(mp[x]==1){
--mp[x];
sbt::erase(x);
if(x>=(md+1)/2){
_1.erase(x);
auto it=_1.upper_bound(x);
int l=md-*it,r=md-1-x;
sbt::modify(l,r,*--it-x);
}else _2.erase(x);
}else{
--mp[x];
if(x<(md+1)/2)_2.erase(x);
}
}
if(t0t<=1)*ww++='E',*ww++='E',*ww++='\n',last=0;else{
last=max({sbt::d[sbt::rt].mx,_2.ask(),big.ask()});
print(last);
}
}
fwrite(bwf,ww-bwf,1,stdout);
return 0;
}