首先把所有数对 $C$ 取模，分类讨论：
- $x+y\geq C$
因为只会取模一次，这时显然取最大值和次大值。
- $x+y<C$
一开始的想法是对于每一个数 $a$ 找到另一个数满足 $a+b<C$ 的最大的 $b$，这样是一棵外向树（环长一定 $=2$），修改如果修改到入度比较大的节点复杂度不对。
接下来是神奇套路：$(a,b)$ 需要被维护当且仅当 $(a,b)$ 互为最优配对。
对于加数，加进去的数 $a$ 寻找一个最优配对 $b$，如果 $b$ 没有被配对直接把 $(a,b)$ 扔进堆里。否则比较 $b$ 的配对 $c$ 和 $a$ 的大小，取较大者和 $b$ 配对，较小者不与任何数配对（一定不会与任何数配对，因为较小数找到的配对数一定是 $b$）。
对于删数，如果 $a$ 没有配对直接删掉，否则把 $(a,b)$ 都删掉，然后插入 $b$。
显然上述操作一定不会遗漏互为最优的配对。
开一个堆维护所有配对，开一个 set 维护所有数，复杂度 $\mathcal O(n\log n)$。注意插入的数中可能有 $0$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct Node{int v,oth;Node(int V,int Oth){v=V,oth=Oth;};};
bool operator <(const Node nd1,const Node nd2){return nd1.v<nd2.v||(nd1.v==nd2.v&&nd1.oth<nd2.oth);}
multiset<Node> st;
struct Delq
{
priority_queue<int> q1,q2;
inline void ins(int x){q1.e(x);}
inline void del(int x){q2.e(x);}
inline void update(){while(q1.size()&&q2.size()&&q1.top()==q2.top())q1.pop(),q2.pop();}
inline int top(){return update(),q1.size()?q1.top():-inf;}
}q;
int n,m;
inline void ins(int x)
{
auto it=st.lower_bound(Node(m-x,-1));int oth=-1;
if(it!=st.begin())
{
--it;Node nd=*it;
if(nd.oth==-1)st.erase(it),st.insert(Node(oth=nd.v,x)),q.ins(nd.v+x);
else
{
if(nd.oth<x)
{
st.erase(it),st.erase(st.find(Node(nd.oth,nd.v)));
st.insert(Node(nd.oth,-1)),st.insert(Node(nd.v,x));
q.del(nd.v+nd.oth),q.ins(nd.v+x),oth=nd.v;
}
}
}
st.insert(Node(x,oth));
}
inline void mian()
{
read(n,m);int opt,x,ans=0;
while(n--)
{
read(opt,x),x=(x^ans)%m;
if(opt==1)ins(x);
else
{
auto it=st.lower_bound(Node(x,-1));Node nd=*it;
if(nd.oth==-1)st.erase(it);
else q.del(nd.oth+nd.v),st.erase(it),st.erase(st.find(Node(nd.oth,nd.v))),ins(nd.oth);
}
ans=q.top();
if(st.size()>=2)Mmax(ans,((--st.end())->v+(--(--st.end()))->v)%m);
if(ans<0)puts("EE"),ans=0;else write(ans,'\n');
}
}