算法:离散化+前缀处理
$O(n*logn)$
首先将所有的点(L,R和其前后可能被用到的点)离散化,记得数组开够!
然后就是按题意进行前缀异或,最后一次O(N) 确定答案,注意一下题目的要求方案!
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,cnt;
const int inf=1e9+2;
struct inp
{
int type,x,y,z;
}a[maxn];
int d[maxn<<2],ans[maxn<<2];
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d",&n);
d[++cnt]=-inf; d[++cnt]=inf; d[++cnt]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].type);
if(a[i].type==1)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
d[++cnt]=a[i].x; d[++cnt]=a[i].y; d[++cnt]=a[i].x-1; d[++cnt]=a[i].y+1;
}
else
{
scanf("%d%d",&a[i].x,&a[i].z);
d[++cnt]=a[i].x; d[++cnt]=a[i].x-1; d[++cnt]=a[i].x+1;
}
}
sort(d+1,d+cnt+1);
cnt=unique(d+1,d+cnt+1)-d-1;
for(int i=1;i<=n;i++)
{
a[i].x=lower_bound(d+1,d+cnt+1,a[i].x)-d;
if(a[i].type==1)
{
a[i].y=lower_bound(d+1,d+cnt+1,a[i].y)-d;
ans[a[i].x]^=a[i].z; ans[a[i].y+1]^=a[i].z;
}
else if(a[i].type==2)
{
ans[a[i].x]^=a[i].z;
ans[a[i].x+1]^=a[i].z;
}
else
{
ans[1]^=a[i].z;
ans[a[i].x]^=a[i].z;
ans[a[i].x+1]^=a[i].z;
}
}
int res=ans[1],number=1;
for(int i=2;i<=cnt;i++)
{
ans[i]^=ans[i-1];
if(ans[i]>res)
{
res=ans[i];
number=i;
}
else if(ans[i]==res && abs(d[i])<=abs(d[number]))
number=i;
}
printf("%d %d",res,d[number]);
return 0;
}