题目链接：联合省选 2020 B D2T1/Luogu P6627/LibreOJ 3308。

位运算题目，容易写炸。

题目

题目描述

为庆祝疫情防治取得重大进展，某商场举行酬宾活动，给顾客一些优惠额度，规则如下：

每位顾客可以任意选择一个整数作为自己的幸运数字。

每位顾客的初始优惠额度为 $0$ 元。

商场有 $n$ 个奖励条件，对应不同的奖励额度 。

每位顾客需要依次比对这 $n$ 个奖励条件，如果该位顾客选择的幸运数字满足第 $i$ 个条件，那么他的优惠额度就会异或上这个条件所对应的奖励额度。

奖励条件共有三种，假设顾客选择的幸运数字为 ：

区间型条件，其有两个参数 $L$ 与 $R$，满足条件为 $L\leq x\leq R$。保证 $L<R$。

相等型条件，其有一个参数 $A$，满足条件为 $x=A$。

不等型条件，其有一个参数 $B$，满足条件为 $x\ne B$。

小炎同学获知了所有奖励条件的信息，他希望知道一位顾客能够得到的最大优惠额度以及对应的幸运数字是多少，请你帮他计算。

数据范围

$20\%$ 的数据满足：$n,|L|,|R|,|A|,|B|\leq 1000$。

$40\%$ 的数据满足：$n\leq 1000$。

$100\%$ 的数据满足：$1\leq n\leq 10^5,|L|,|R|,|A|,|B|\leq 10^9,1\leq w _ i\leq 10^9$。

时空限制

题目编号	时间限制	空间限制
联合省选 2020 B D2T1	$1\text{s}$	$256\text{MiB}$

题解

解法 A（暴力）

$20\%$ 的数据满足：$n,|L|,|R|,|A|,|B|\leq 1000$。

---

我们不妨枚举 $x\in[-1001,1001]$，然后直接统计即可。

时间复杂度为 $\Theta(n|S|)$，其中 $|S|=1001+1001+1=2003$，期望得分 $20$ 分。

解法 B（离散化+暴力）

$40\%$ 的数据满足：$n\leq 1000$。

---

其实就是 解法 A 的值域变大了而已，我们可以简单离散化一下，离散化的时候要注意，要插入 $0$，$\max\{R\}+1$ 和 $\min\{L\}-1$ 三个值，预防答案是这几个数字，对于第三种操作，还要插入 $B-1$，$B+1$。

这种做法的复杂度为 $\Theta(n\log _ 2n+n^2)$，期望得分为 $40$ 分。

解法 C（容易写错的正解）

$100\%$ 的数据满足：$1\leq n\leq 10^5,|L|,|R|,|A|,|B|\leq 10^9,1\leq w _ i\leq 10^9$。

---

离散化后用线段树维护即可，离散化的时候容易出错，务必小心。

时间复杂度为 $\Theta(n\log _ 2n)$，期望得分 $100$ 分，实际上很容易写错（离散化出错导致数组越界进而 $\texttt{RE}$），得分往往只有 $20\to 30$ 分。

解法 D（正解）

$100\%$ 的数据满足：$1\leq n\leq 10^5,|L|,|R|,|A|,|B|\leq 10^9,1\leq w _ i\leq 10^9$。

---

别离散化，用 map 更保险，别区间操作，换一换更保险。

1. 区间操作：$a _ L\oplus w$，$a _ {R+1}\oplus w$。
2. 单点操作：$a _ A\oplus w$，$a _ {A+1}\oplus w$。
3. 非单点操作：$\texttt{base}\oplus w$，$a _ B\oplus w$。

用 map 把每个点应该异或上的值存起来，最后丢到 pair 里，扫一遍即可。

也有一些细节要注意，记得特判 $0$。

时间复杂度 $\Theta(n\log _ 2+n)$。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

int n,base;
int ans=-INF,pos=-INF;
vector<pair<int,int>/**/> T;
map<int,int> M;

inline void update(reg int x){
    if(abs(x)<abs(pos))
        pos=x;
    else if(abs(x)==abs(pos)&&x>pos)
        pos=x;
    return;
}

int main(void){
    n=read();
    for(reg int i=1;i<=n;++i){
        static int opt,l,r,v;
        opt=read();
        switch(opt){
            case 1:{
                l=read(),r=read()+1,v=read();
                break;
            }
            case 2:{
                l=read(),r=l+1,v=read();
                break;
            }
            case 3:{
                l=read(),r=l+1,v=read();
                base^=v;
                break;
            }
            default:break;
        }
        M[l]^=v,M[r]^=v;
    }
    for(map<int,int>::iterator it=M.begin();it!=M.end();++it)
        T.push_back(make_pair(it->first,it->second));
    T.push_back(make_pair(-INF,0)),
    T.push_back(make_pair(INF,0));
    sort(T.begin(),T.end());
    reg int pre=base;
    for(reg int i=0,size=T.size();i<size-1;++i){
        pair<int,int> p=T[i];
        pre^=p.second;
        if(pre>ans){
            ans=pre,pos=p.first;
            update(T[i+1].first-1);
            if(p.first<=0&&0<=T[i+1].first-1)
                pos=0;
        }
        else if(pre==ans){
            update(p.first),update(T[i+1].first-1);
            if(p.first<=0&&0<=T[i+1].first-1)
                pos=0;
        }
    }
    printf("%d %d\n",ans,pos);
    return 0;
}