自动搬运

查看原文

来自洛谷，原作者为

	Owen_codeisking 前OIer/ACMer/柚子厨/酒姬民

搬运于2025-08-24 22:17:28，当前版本为作者最后更新于2020-02-16 19:26:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

比赛时 T2 忘开 long long 自闭了好长时间，这是赛后写的。

好像这题还蛮套路的？

首先我们先分类讨论（加入集合 $S$ 时已取模）：

1. $C\le i+j<2\times C$，因为 $0\le i,j< C$，所以取个最大值和次大值就行了。

2. $0\le i+j<C$，这样的话每个数 $i$ 会有一个最佳匹配 $j$，使得 $i+j$ 最接近 $C-1$。显然这个匹配是单向的。

若此题离线，那么考虑线段树分治，每次加进去的时候把这个数的最佳匹配找出来，对答案取个 $\max$。时间 $O(n\log^2 n)$。

现在考虑在线。若删除的话，有可能这个数是多个数的最佳匹配，那么一次删除涉及最多 $O(|S|)$ 次重新匹配，显然不可取。

那么我们换个角度考虑，只维护双向匹配的对数，这样每次修改只涉及 $O(1)$ 对，时间就对了。

为什么呢？

一般这种最优化数对的题，都是先弄出个 $O(n^2)$ 的解法，再看看这些对数是否满足什么限制，使得某个数对 $(i,j)$ 一定比 $(j,k)$ 优，这些数对一定很少且一次修改涉及的对数不多，所以我们只需要维护这些数对。

假设 $i$ 的最优匹配是 $j$，$j$ 的最优匹配是 $k$。若 $i<k$，那么只需考虑 $(j,k)$ 这一数对。

这样的数对显然最多 $O(n)$ 个，用 $\text{multiset}$ 维护最优匹配，时间 $O(n\log n)$。

不过你一次修改需要找出这个数的最优匹配，最优匹配的最优匹配，最优匹配的最优匹配的最优匹配，常数比较大，细节有一点。建议画个图把细节理清楚再写。还有，$\text{stl}$ 的边界要格外小心。

最短代码 $\text{1.13k}$：

#include <bits/stdc++.h>
using namespace std;
int n,c,sz;
multiset<int> a,b;
multiset<int>::iterator it;
inline int best(int x,int op)
{
	if(x==-1) return -1;
	it=a.upper_bound(c-1-x);
	if(it==a.begin()) return -1;
	it--;
	if(op==1 && *it==x && a.count(x)==1)
		return (it==a.begin())?-1:*--it;
	else
		return *it;
}
inline void insert(int x)
{
	sz++;
	if(sz==1) { a.insert(x); return; }
	int y=best(x,0),z=best(y,1),w=best(z,1);
	if(y!=-1 && z<x)
	{
		if(z!=-1 && y==w) b.erase(b.find(y+z));
		b.insert(x+y);
	}
	a.insert(x);
}
inline void erase(int x)
{
	a.erase(a.find(x)),sz--;
	if(!sz) return;
	int y=best(x,0),z=best(y,1),w=best(z,1);
	if(y!=-1 && z<x)
	{
		if(z!=-1 && y==w) b.insert(y+z);
		b.erase(b.find(x+y));
	}
}
inline int query()
{
	it=--a.end();
	if(a.count(*it)>=2) return *it*2%c;
	else return (*it+*--it)%c;
}
int main()
{
	scanf("%d%d",&n,&c);
	int op,x,lastans=0;
	while(n--)
	{
		scanf("%d%d",&op,&x); x^=lastans;
		if(op==1) insert(x%c);
        else erase(x%c);
		if(sz<2) puts("EE"),lastans=0;
		else printf("%d\n",lastans=max(query(),b.empty()?0:*--b.end()));
	}
	return 0;
}

（估计我大括号不换行会更短）

题出得好！难度适中，覆盖知识点广，码量不大，解法比较自然，给出题人点赞！

就是没啥 gal 的背景，差评

upd: 好像不能每次都过？