[Ynoi2010] y-fast trie(multiset+思维)

题目传送门

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;
}