这可能也是一个关于匹配的经典 trick。
题意
给定常数 \(C\)，你需要维护一个集合 \(S\)，支持以下操作：
1 x，加入数 \(x\)，保证 \(x\) 之前不存在。2 x，删除数 \(x\)，保证 \(x\) 之前存在。
每次操作后你需要回答 $$\max_{i,j\in S,i\not=j}(i+j)\bmod C$$
\(Q\le 5\times10^5\)，强制在线。
分析
首先，将 \(x\) 模 \(C\) 处理后，对答案显然没有影响。但需要注意的是，模 \(C\) 处理后 \(x\) 就有可能会有重复了。
显然当集合大小小于 2 时无解，下文不讨论这种情况。
套路性的将 \((i+j)\bmod C\) 分成两种贡献讨论：\(i+j\ge C,i+j<C\)。第一种贡献显然是好处理的，只需要取集合的最大值和次大值相加即可。
对于第二种贡献，对于每个数 \(i\)，找到能使 \(i+j<C\) 且 \(i+j\) 最大的 \(j\)，把这些数对 \((i,j)\) 扔进另一个 set 里。显然 \(j\) 就是集合中 \(C-1-i\) 的前驱。但是删除的时候，可能一个数是多个数的最优匹配，当删除该数后，我们需要重新计算这些数的最优匹配，然后就上天了。
如果没有强制在线，我们可以线段树分治掉。但是强制在线，我们需要考虑另外一个做法。
注意到很多的数对 \((i,j)\) 是没有用的，不会参与计算。具体地，对于 \(i,j,k\)，若 \(j\) 是 \(i\) 的最优匹配，\(k\) 是 \(j\) 的最优匹配，那么 \((i,j)\) 一定是没用的。那么我们只需要维护双向匹配的那些数对就行了，显然这样的数对只有 \(O(n)\) 个，删除时也只会删掉至多一个数对，删除数对后就相当于把数对没被删掉的那一项“删掉再重新插入”到集合当中，这样复杂度就是正确的了。时间复杂度 \(O(n\log n)\)。注意寻找最优匹配时要避免自己跟自己匹配。
笑点解析：set 的 rbegin 返回的反向迭代器。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define IOS ios::sync_with_stdio(false)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("EE")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define un using namespace
#define popc __builtin_popcountll
#define all(x) x.begin(),x.end()
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
using pii=pair<int,int>;
using i64=long long;
using u64=unsigned long long;
template<typename T>bool greating(T x,T y){return x>y;}
inline int rd(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}return x*f;
}
template<typename T>
inline void write(T x,char ch='\0'){if(x<0){x=-x;putchar('-');}int y=0;char z[40];while(x||!y){z[y++]=x%10+48;x/=10;}while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=2e5+5,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int Q,mod;
multiset<int>s,ans;
inline int fnd(int x){int val=mod-1-x;auto it=s.upper_bound(val);if(it==s.begin())return -1;--it;return *it;
}
map<int,int>mt;
inline void ins(int x){if(s.empty())return s.emplace(x),void();int y=fnd(x);s.emplace(x);if(y==-1||mt[y]==x+1)return;s.erase(s.find(y));int z=fnd(y);s.emplace(y);if(x==z){if(mt[y]){int w=mt[y]-1;mt[y]=mt[w]=0,ans.erase(ans.find(y+w));}mt[y]=x+1,mt[x]=y+1;ans.emplace(x+y);}
}
inline void del(int x){int y=mt[x]-1;mt[x]=0;s.erase(s.find(x));if(y==-1)return;mt[y]=0;ans.erase(ans.find(x+y));s.erase(s.find(y));ins(y);
}
inline void solve_the_problem(){Q=rd(),mod=rd();int lstans=0;while(Q--){int op=rd(),x=rd();x^=lstans;x%=mod;op==1?ins(x):del(x);if(s.size()<=1){PW,lstans=0;continue;}write(lstans=max((*s.rbegin()+*(++s.rbegin()))%mod,ans.empty()?0:*ans.rbegin()),10);}
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);int _=1;while(_--)solve_the_problem();
}
/*
4 9
1 1
1 2
1 2
2 2
*/
