P6627 [省选联考 2020 B 卷] 幸运数字

*原题链接*

并不是非常难的题，不过细节非常多。

首先大题思路很明确，把所有条件储存下来，把这些l，r，x啥的离散化，然后区间异或，最后查询最大值。至于区间异或用差分就好了，因为异或一个数两次等于没异或。

不过就出问题了，因为我们在差分操作的时候可能会涉及某些区间的端点，为了防止漏掉这些情况，就把L-1，R+1，x-1，x+1都加入离散化数组。

不过最后依然还有细节问题，因为我们没考虑0。如果一个区间[l,r]中包含0，而我们离散化数组中未加入0值，那么就会出错，最后喜提WA90。

思路理顺后，代码也并不难写。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;//fast read
int read(){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*10+ch-'0',ch=getchar();return x*f;
}int n,lsh[N],tot,cnt,a[N],d[N],w[N],ty[N],l[N],r[N];signed main(){n=read();lsh[++tot]=0;//注意加入0值for(int i=1;i<=n;i++){ty[i]=read();if(ty[i]==1){l[i]=read(),r[i]=read();lsh[++tot]=l[i],lsh[++tot]=r[i],lsh[++tot]=l[i]-1,lsh[++tot]=r[i]+1;}else if(ty[i]==2){l[i]=read();lsh[++tot]=l[i],lsh[++tot]=l[i]-1,lsh[++tot]=l[i]+1;}else{l[i]=read();lsh[++tot]=l[i],lsh[++tot]=l[i]-1,lsh[++tot]=l[i]+1;}w[i]=read();}sort(lsh+1,lsh+1+tot),cnt=unique(lsh+1,lsh+1+tot)-lsh-1;for(int i=1;i<=n;i++) l[i]=lower_bound(lsh+1,lsh+1+cnt,l[i])-lsh;//离散化//处理询问for(int i=1;i<=n;i++){if(ty[i]==1){r[i]=lower_bound(lsh+1,lsh+1+cnt,r[i])-lsh;d[l[i]]^=w[i],d[r[i]+1]^=w[i];}else if(ty[i]==2){d[l[i]]^=w[i],d[l[i]+1]^=w[i];}else{d[1]^=w[i],d[l[i]]^=w[i],d[l[i]+1]^=w[i];}}//查询int ans=d[1],pos=1;for(int i=2;i<=cnt;i++){d[i]^=d[i-1];if(d[i]>ans) ans=d[i],pos=i;else if(d[i]==ans&&abs(lsh[i])<=abs(lsh[pos])) pos=i;}cout<<ans<<" "<<lsh[pos]<<endl;return 0;
}