「联合省选 2020 B」幸运数字 题解

问题分析

这个问题要求找到使优惠额度（异或和）最大的幸运数字 $x$。三种奖励条件可以统一处理为在特定区间上进行异或操作。

关键观察

• 区间型条件 $(L \leq x \leq R)$：在区间 $[L, R]$ 上异或 $w_i$
• 相等型条件 $(x = A)$：在单点 $A$ 上异或 $w_i$，可视为区间 $[A, A]$
• 不等型条件 $(x \neq B)$：在区间 $(-\infty, B-1] \cup [B+1, +\infty)$ 上异或 $w_i$

算法思路

1. 离散化处理

由于值域范围很大（$[-10^9, 10^9]$），但操作数 $n \leq 10^5$，使用离散化技术：

void updata(int v) {
    num[++tot] = v - 1, num[++tot] = v, num[++tot] = v + 1;
}

提取所有可能的关键点：

• 每个参数的 $v-1$, $v$, $v+1$
• 初始加入 $0$ 点

2. 差分数组技巧

使用差分数组处理区间异或操作：

对于区间 $[l, r]$ 异或 $w$：

• val[l] ^= w
• val[r+1] ^= w

3. 条件类型处理

if (a != INF && b != INF)          // 区间型 [A,B]
    val[a] ^= w[i], val[b + 1] ^= w[i];
else if (a != INF)                 // 相等型 [A,A]  
    val[a] ^= w[i], val[a + 1] ^= w[i];
else if (b != INF)                 // 不等型 (-∞,B-1]∪[B+1,+∞)
    val[1] ^= w[i], val[b] ^= w[i], val[b + 1] ^= w[i], val[_tot + 1] ^= w[i];

代码实现分析

1. 离散化关键点收集

num[++tot] = 0;  // 初始基准点
rep(i, 1, n) {
    if (opt == 1) {
        cin >> A[i] >> B[i] >> w[i];
        updata(A[i]), updata(B[i]);
    } else if (opt == 2) {
        cin >> A[i] >> w[i], B[i] = INF;
        updata(A[i]);
    } else if (opt == 3) {
        cin >> B[i] >> w[i], A[i] = INF;
        updata(B[i]);
    }
}

2. 排序去重与映射

sort(num + 1, num + tot + 1);
int _tot = unique(num + 1, num + tot + 1) - num - 1;

3. 差分数组应用

rep(i, 1, _tot) val[i] ^= val[i - 1];  // 前缀异或还原实际值

4. 最优解选择

rep(i, 1, _tot) {
    if (val[i] > mxval)
        mxval = val[i], ans = num[i];
    else if (val[i] == mxval) {
        if (abs(ans) > abs(num[i]))
            ans = num[i];
        else if (abs(ans) == abs(num[i]))
            ans = max(ans, num[i]);
    }
}

复杂度分析

• 离散化：$O(n \log n)$ 排序去重
• 差分操作：$O(n)$ 处理所有条件
• 前缀计算：$O(n)$ 还原实际值
• 总复杂度：$O(n \log n)$，适合 $n \leq 10^5$

算法标签

🏷️ 主要算法

离散化 - 将大值域映射到有限关键点 差分数组 - 高效处理区间异或操作 扫描线 - 按顺序处理关键点

🏷️ 数据结构

数组映射 - 存储离散化后的坐标关系 排序算法 - 对关键点排序处理

🏷️ 优化技术

区间转化 - 统一处理三种条件类型 关键点提取 - 只处理可能改变结果的位置 前缀异或 - 快速还原区间操作结果

🏷️ 问题类型

区间修改查询 - 在值域上进行区间异或操作 最优化问题 - 寻找最大异或和对应的数字 离散化处理 - 处理大范围值域问题

这个解决方案通过巧妙的离散化和差分数组技术，将原本需要处理 $10^9$ 量级值域的问题转化为 $O(n \log n)$ 的高效算法，充分体现了离散化在处理大范围数据中的威力。