题解 P6627 【[省选联考 2020 B 卷] 幸运数字】

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