题目传送门
solution
妙妙题。
分成 \(a+b\geq C\) 和 \(a+b<C\) 讨论。
第一类是简单的，只需要选择最大和次大的数就行了。
第二类加入是容易的，但是有删除。
常规做法是线段树分治+\(multiset\)，不能在线。
考虑一个性质：
如果对于 \(x\)，小于等于 \(C-1-x\) 的最大的 \(y\) 记作 \(mat(x)\) 。
那么如果 \(mat(mat(x))\neq x\)，则 \(mat(x)+mat(mat(x))\) 一定大于 \(x+mat(x)\) 。
换句话说，只有 "双向" 的匹配关系是有用的。
那么加入和删除一个数的时候，"双向"匹配的变化量显然是 \(O(1)\) 的，再用一个 \(multiset\) 维护所有双向匹配的值就好了。
复杂度 \(O(n\log n)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+7;
multiset<int> num,ans;
int n,C;
int match(int x,int c)
{
if(x==-1)return -1;
auto it=num.upper_bound(C-1-x);
if(it==num.begin())return -1;
it--;
if(c&&(*it)==x&&num.count(x)==1)
{
if(it==num.begin())return -1;
return *(--it);
}
return *it;
}
void ins(int x)
{
if(num.empty())
{
num.insert(x);
return;
}
int y=match(x,0),z=match(y,1),w=match(z,1);
if(y!=-1&&x>z)
{
if(z!=-1&&y==w) ans.erase(ans.find(y+z));
ans.insert(x+y);
}
num.insert(x);
}
void del(int x)
{
num.erase(num.find(x));
if(num.empty())return;
int y=match(x,0),z=match(y,1),w=match(z,1);
if(y!=-1&&x>z)
{
if(z!=-1&&y==w) ans.insert(y+z);
ans.erase(ans.find(x+y));
}
}
int query()
{
int res=0;
auto it=(--num.end());
if(num.count(*it)>1) res=max(res,(*it)*2%C);
else res=max(res,((*it)+(*--it))%C);
if(!ans.empty())res=max(res,*(--ans.end()));
return res;
}
int main()
{
cin>>n>>C;
int lst=0;
while(n--)
{
int op,x;
scanf("%d %d",&op,&x);
x=(x^lst)%C;
if(op==1)ins(x%C);
if(op==2)del(x%C);
if(num.size()<2)
{
printf("EE\n");
lst=0;
}
else printf("%d\n",lst=query());
}
return 0;
}