算法模板2：位运算+离散化+区间合并

1.6 位运算

位运算是直接在二进制位上进行操作的运算。位运算通常用于优化算法，尤其是当涉及到数字处理、快速计算和空间优化

1. 按位与 & （AND）

• 操作规则：当两个二进制数的对应位都为1时，结果才为1，否则为0。

  1010
  & 1101
  ------
  1000
  

  • 检查某一位是否为1： 例如，n & (1 << k) 判断第k位是否为1。如果为1，结果不为0；否则为0。
  • 清除最低位的1： n & (n - 1) 会将n的最低位1变成0。

2. 按位或 | （OR）

• 操作规则：当两个二进制数的对应位中至少有一个为1时，结果为1。

  1010
  | 1101
  ------
  1111
  

  • 设置某一位为1： n | (1 << k) 将第k位置为1。

3. 按位异或 ^ （XOR）

• 操作规则：当两个二进制数的对应位相异时，结果为1，否则为0。

  1010
  ^ 1101
  ------
  0111
  

  • 翻转某一位： n ^ (1 << k) 将第k位的值翻转（1变成0，0变成1）。
  • 检查两个数是否相等： a ^ b == 0 表示a与b相等。

4. 按位非 ~ （NOT）

• 操作规则：对每一位取反，1变成0，0变成1。

  ~ 1010
  ------
  0101
  

5. 左移 << （Left Shift）

• 操作规则：将二进制数的所有位向左移动指定的位数，左移时低位补0，高位丢弃。

  1010 << 1 = 10100
  

  • 乘以2：n << 1 相当于将n乘以2。
  • 高速计算乘法：左移可以用来快速计算n的2的幂次方倍数。

6. 右移 >> （Right Shift）

• 操作规则：将二进制数的所有位向右移动指定的位数，右移时高位补符号位（有符号数时补1，没符号数时补0）。

  1010 >> 1 = 0101
  

  • 除以2：n >> 1 相当于将n除以2。
  • 高速计算除法：右移可以用来快速计算n的2的幂次方除法。

7. 获取某一位的值

n >> k & 1

• 说明：n >> k 将n右移k位，然后与1做按位与运算，这样可以获取n的第k位数字（0或1）。

8. 获取n的最后一位1

lowbit(n) = n & -n

• 说明：n & -n 用来得到n的最后一位1。例如，n = 12 (1100) 时，lowbit(n) 的结果为 4 (0100)。
  • -n 是n的二进制补码表示，n & -n 会保留n的最后一位1，并将其他所有位清零。

位运算的常见应用

1. 判断奇偶性：
   • 通过 n & 1 判断n是否为奇数（如果结果是1则n为奇数）。
2. 快速计算2的幂：
   • 使用 1 << k 来计算 2^k。
3. 检查二进制表示中是否只有一个1：
   • n & (n - 1) == 0 可以检查n是否为2的幂（如果n只包含一个1）。
4. 统计二进制中1的个数：
   • __builtin_popcount(n) 或 while (n) {n &= (n - 1);}，每次去掉最右边的1。
5. 交换两个数：
   • a ^= b; b ^= a; a ^= b; 可以用异或交换两个数。
6. 清除低位的1：
   • n & (n - 1) 会把n的最低位的1清除。
7. 模拟集合：
   • 通过位运算可以模拟集合的操作，如 set、union、intersection 等。例如，n 可以表示一个集合，其中第k位表示是否包含元素k。

1.7 离散化

核心作用：将数值范围较大的数据映射到一个较小的连续整数范围，便于在数组、前缀和、差分、树状数组、线段树等数据结构中操作。

主要解决值域大、数据稀疏的问题，结合其他算法实现高效求解，如扫描线、差分数组、树状数组和线段树等。

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

经典离散化题目例子

1. 区间合并和覆盖长度问题

题目：给定 n 个区间 [li,ri][l_i, r_i]，求所有区间的覆盖总长度（去重后的长度）。

• 分析：原区间可能范围很大（如 [1,109][1, 10^9]），无法直接操作。通过离散化，将所有区间端点压缩到较小范围。

• 思路

  1. 离散化所有区间的端点。
  2. 用差分数组或扫描线记录区间变化，统计覆盖长度。

2. 区间查询与修改

题目：有 n 个点，每次给区间 [l,r][l, r] 增加一个值 cc，并查询某个点的最终值。

• 分析：区间范围过大（如 1∼1091 \sim 10^9），通过离散化压缩到有限范围。

• 思路

  1. 离散化所有可能的坐标。
  2. 使用差分数组、树状数组或线段树进行区间操作。

3. 动态求第 K 小值

题目：有 n 个操作，每次插入一个值或查询当前数据的第 k 小值。

• 分析：可能有很大的值范围（如 [1,109][1, 10^9]），通过离散化解决大范围权值问题。

• 思路

  1. 离散化所有插入的值。
  2. 用树状数组或线段树统计权值频次。

4. 区间最大重叠次数

题目：给定 n 个区间，求区间重叠最多的时间点及重叠次数。

• 分析：时间点范围可能很大，需离散化区间端点。

• 思路

  1. 离散化所有区间端点。
  2. 使用扫描线或差分数组统计每个离散点的重叠次数。

5. 动态逆序对计数

题目：给定一个初始数组，每次插入一个值，实时输出数组的逆序对个数。

• 分析：插入值可能范围过大（如 [1,109][1, 10^9]），需离散化值域。

• 思路

  1. 离散化所有可能的值。
  2. 用树状数组或线段树动态维护逆序对。

6. 二维区间问题

题目：给定 n 个矩形，求哪些矩形有重叠区域或总覆盖面积。

• 分析：矩形坐标范围可能很大，需对 x 和 y 坐标分别离散化。

• 思路

  1. 对 x 和 y 轴分别离散化，压缩到二维数组。
  2. 使用二维差分或扫描线处理。

7. 模拟车流/时间段事件

题目：给定 n 个车辆的进入和离开时间，求某时刻停车场中车辆的数量。

• 分析：时间范围可能很大（如 [1,109][1, 10^9]），需离散化时间点。

• 思路

  1. 离散化所有进入和离开的时间点。
  2. 使用差分数组统计每个时间点的车辆变化。

8. 区间众数统计

题目：给定一个数组，支持动态查询任意区间内的众数。

• 分析：值域较大（如 [1,109][1, 10^9]），需离散化元素值。

• 思路

  1. 离散化数组中的值。
  2. 用莫队算法或树状数组分块统计。

具体例题

1. 区间统计问题：Leetcode 56 合并区间。
2. 动态第 k 小问题：Leetcode 315 计算右侧小于当前元素的个数。
3. 区间重叠次数：AcWing 1240 最大区间重叠。
4. 动态逆序对计数：Leetcode 493 翻转对。
5. 二维差分矩阵：AcWing 1226 最大矩形面积。

1.8 区间合并

using PII = pair<int, int>;

// 合并区间的函数
void merge(vector<PII> &segs) {
    vector<PII> res;
    // 1. 按起点排序，如果起点相同，按终点排序
    sort(segs.begin(), segs.end());
    // 2. 初始化st和ed为不可能出现的值
    int st = -2e9, ed = -2e9;
    // 3. 遍历所有区间
    for (auto seg : segs) {
        if (ed < seg.first) { // 当前区间与前一个区间不重叠
            if (st != -2e9) res.push_back({st, ed}); // 把上一个区间加入结果
            st = seg.first;  // 更新st
            ed = seg.second; // 更新ed
        } else { // 当前区间与前一个区间重叠
            ed = max(ed, seg.second); // 合并区间，更新ed
        }
    }
    // 4. 最后一个区间加入结果
    if (st != -2e9) res.push_back({st, ed});

    egs = res; // 更新输入数组
}