自动搬运

查看原文

来自洛谷，原作者为

	VenusM1nT 醉后不知天在水 满船清梦压星河 | 明日方舟群 348956527

搬运于2025-08-24 22:22:34，当前版本为作者最后更新于2020-09-01 22:19:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

离散化 + 差分。
（好久没写代码了，手有点生，见谅）
观察数据范围，发现代表范围的数据在 $10^9$ 这个级别，而代表点数的 $n\leq 10^5$，于是考虑离散化。
对于条件 1，因为幸运数字可能等于端点，因此要把 $L-1$ 和 $R+1$ 这两个数字加入离散化数组中；条件 2 和 3 同理，考虑是否等于端点，因此加入 $A-1$ 和 $A+1$ 这两个数字。同时为了保证答案的正确性（绝对值最小），而最后的答案肯定是在离散化数组中取到，因此加入 0 这个数字。（很多题解都加了 $\pm \inf$ 这个值，但我认为既然要绝对值最小那应该就是在端点位置取到的答案，所以不用加。而不加确实也可以通过此题，不知道是不是数据的问题）
接下来就是差分了，由于对一个数字异或两次数是不变的，所以直接对每个离散化完的点大力异或就可以了。
具体见代码。

#include<bits/stdc++.h>
#define MAXN 100005
#define reg register
#define inl inline
#define inf 1e9
using namespace std;
int n,opt[MAXN],l[MAXN],r[MAXN],val[MAXN],pos[MAXN<<2],tot,ans,Ans,cnt[MAXN<<2];
int main()
{
	scanf("%d",&n);
	pos[++tot]=0;
	for(reg int i=1;i<=n;i++)
	{
		scanf("%d",&opt[i]);
		if(opt[i]==1)
		{
			scanf("%d %d %d",&l[i],&r[i],&val[i]);
			pos[++tot]=l[i]; pos[++tot]=r[i];
			pos[++tot]=l[i]-1; pos[++tot]=r[i]+1;
		}
		else
		{
			scanf("%d %d",&l[i],&val[i]);
			pos[++tot]=l[i]; pos[++tot]=l[i]-1; pos[++tot]=l[i]+1;
		}
	}
	sort(pos+1,pos+tot+1);//离散化
	tot=unique(pos+1,pos+tot+1)-pos-1;
	for(reg int i=1;i<=n;i++)//差分
	{
		l[i]=lower_bound(pos+1,pos+tot+1,l[i])-pos;
		if(opt[i]==1)
		{
			r[i]=lower_bound(pos+1,pos+tot+1,r[i])-pos;
			cnt[l[i]]^=val[i];
			cnt[r[i]+1]^=val[i];
		}
		else if(opt[i]==2)
		{
			cnt[l[i]]^=val[i];
			cnt[l[i]+1]^=val[i];
		}
		else if(opt[i]==3)
		{
			cnt[1]^=val[i];
			cnt[l[i]]^=val[i];
			cnt[l[i]+1]^=val[i];
		}
	}
	ans=cnt[1];
	Ans=1;
	for(reg int i=2;i<=tot;i++)//找最优解
	{
		cnt[i]^=cnt[i-1];
		if(cnt[i]>ans)
		{
			ans=cnt[i];
			Ans=i;
		}
		else if(cnt[i]==ans && abs(pos[i])<=abs(pos[Ans])) Ans=i;
	}
	printf("%d %d\n",ans,pos[Ans]);
	return 0;
}