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

· · 题解

题目链接：传送门

思路：

观察到 1\leq n\leq 10^5 而 |L|,|R|,|A|,|B|\leq 10^9 ，考虑将 L , R , A , B 离散化，让他们都在 n 的范围内，此时我们得到了一个空的序列，题目区间的端点都被映射到了序列上。

对于三种操作，我们都可以将其转换为区间操作：

1.对于 t_i=1 的数据，将区间 [L,R] 上所有的值 \oplus ~ w_i

2.对于 t_i=2 的数据执行单点修改，即将区间 [A,A]~\oplus ~ w_i

3.对于 t_i=3 的数据，可以修改区间 (-∞,B)\cup(B,+∞) ，也可以根据异或的性质，先对全局进行修改，然后再对区间 [B,B]~\oplus ~ w_i

这样你就拿到了20pts

由于异或对答案的贡献不一定为正，所以在离散化时我们应将区间端点的左右节点考虑进去，即：

L-1,R+1,A-1,A+1,B-1,B+1

因为题目要求输出绝对值最小的数字当中值最大的，所以答案只会出现在这些端点上。

对于区间修改操作，可以使用差分数组，本人写的是线段树，用延迟标记来维护区间修改。由于只用查询一次，查询的时候可以直接查询线段树的叶子节点并记录答案，最后 \mathcal{O(n)} 扫出最大值。

题目要求输出绝对值最小的数字当中值最大的，可以建立一个结构体并重载运算符，排序后直接输出答案。

代 码 放 送：

既然你能找到这题，我相信你能瞬间做出来的。

Code: 
#include<bits/stdc++.h>
#define Max(x,y) (x>y?x:y)
#define Min(x,y) (x<y?x:y)
using namespace std;
const long long N=100010,M=1000010,INF=0x3f3f3f3f;
long long n,a[M<<2],b[M<<2],Ans[M<<4],cnt1,cnt2,cnt3,ans_mx=-INF;
struct node{
    long long t,L,R,A,B,w;
}e[M<<2];
struct Ans{
    long long Sum,Abs;
    bool operator <(const Ans &a)const{
        return(Abs!=a.Abs)?Abs<a.Abs:Sum>a.Sum;
    }
}ans[M];
struct SegmentTree{
    long long l,r;
    long long add;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define add(x) tree[x].add
}tree[M<<2];
void init(){
    sort(a+1,a+cnt1+1);
    for(long long i=1;i<=cnt1;i++)
        if(i==1||a[i]!=a[i-1])b[++cnt2]=a[i];
}
long long query(long long x){
    return lower_bound(b+1,b+cnt2+1,x)-b;
}
void Build(long long x,long long l,long long r){
    l(x)=l,r(x)=r;
    if(l==r)return;
    long long mid=(l+r)>>1;
    Build(x<<1,l,mid);
    Build(x<<1|1,mid+1,r);
}
void Change(long long x,long long L,long long R,long long d){
    long long l=l(x),r=r(x);
    if(L<=l&&r<=R){
        add(x)^=d;
        return;
    }
    long long mid=(l+r)>>1;
    if(L<=mid)Change(x<<1,L,R,d);
    if(R>mid)Change(x<<1|1,L,R,d);
}
void Query(long long x,long long d){
    d^=add(x);
    long long l=l(x),r=r(x);
    if(l==r){Ans[l]=d;return;}
    Query(x<<1,d);
    Query(x<<1|1,d);
}
int main(){
    scanf("%lld",&n);
    a[++cnt1]=-INF,a[++cnt1]=0,a[++cnt1]=INF;
    for(long long i=1;i<=n;i++){
        scanf("%lld",&e[i].t);
        if(e[i].t==1){
            scanf("%lld%lld%lld",&e[i].L,&e[i].R,&e[i].w);
            a[++cnt1]=e[i].L;
            a[++cnt1]=e[i].R;
            a[++cnt1]=e[i].L-1;
            a[++cnt1]=e[i].R+1;
        }
        if(e[i].t==2){
            scanf("%lld%lld",&e[i].A,&e[i].w);
            a[++cnt1]=e[i].A;
            a[++cnt1]=e[i].A-1;
            a[++cnt1]=e[i].A+1;
        }
        if(e[i].t==3){
            scanf("%lld%lld",&e[i].B,&e[i].w);
            a[++cnt1]=e[i].B;
            a[++cnt1]=e[i].B-1;
            a[++cnt1]=e[i].B+1;
        }
    }
    init();
    Build(1,1,cnt2);
    for(long long i=1;i<=n;i++){
        if(e[i].t==1){
            long long L=query(e[i].L);
            long long R=query(e[i].R);
            Change(1,L,R,e[i].w);
        }
        if(e[i].t==2){
            long long A=query(e[i].A);
            Change(1,A,A,e[i].w);
        }
        if(e[i].t==3){
            long long B=query(e[i].B);
            if(B>1)Change(1,1,B-1,e[i].w);
            if(B<cnt2)Change(1,B+1,cnt2,e[i].w);
        }
    }
    Query(1,0);
    for(long long i=1;i<=cnt2;i++)
        ans_mx=Max(ans_mx,Ans[i]);
    for(long long i=1;i<=cnt2;i++)
        if(ans_mx==Ans[i]){
            ans[++cnt3].Sum=b[i];
            ans[cnt3].Abs=abs(b[i]);
        }
    sort(ans+1,ans+cnt3+1);
    printf("%lld %lld\n",ans_mx,ans[1].Sum);
    return 0;
}