网站模版防被偷,wordpress如何生成html代码,婚纱网站目录优化,做网站备案需要什么文章目录 1.6 位运算**位运算的常见应用**1.7 离散化**经典离散化题目例子****1. 区间合并和覆盖长度问题****2. 区间查询与修改****3. 动态求第 K 小值****4. 区间最大重叠次数****5. 动态逆序对计数****6. 二维区间问题****7. 模拟车流/时间段事件****8. 区间众数统计** **具… 文章目录 1.6 位运算**位运算的常见应用**1.7 离散化**经典离散化题目例子****1. 区间合并和覆盖长度问题****2. 区间查询与修改****3. 动态求第 K 小值****4. 区间最大重叠次数****5. 动态逆序对计数****6. 二维区间问题****7. 模拟车流/时间段事件****8. 区间众数统计** **具体例题** 1.8 区间合并 1.6 位运算
位运算是直接在二进制位上进行操作的运算。位运算通常用于优化算法尤其是当涉及到数字处理、快速计算和空间优化
按位与 AND 操作规则当两个二进制数的对应位都为1时结果才为1否则为0。 10101101
------
1000检查某一位是否为1 例如n (1 k) 判断第k位是否为1。如果为1结果不为0否则为0。清除最低位的1 n (n - 1) 会将n的最低位1变成0。
按位或 | OR 操作规则当两个二进制数的对应位中至少有一个为1时结果为1。 1010
| 1101
------
1111设置某一位为1 n | (1 k) 将第k位置为1。
按位异或 ^ XOR 操作规则当两个二进制数的对应位相异时结果为1否则为0。 1010
^ 1101
------
0111翻转某一位 n ^ (1 k) 将第k位的值翻转1变成00变成1。检查两个数是否相等 a ^ b 0 表示a与b相等。
按位非 ~ NOT 操作规则对每一位取反1变成00变成1。 ~ 1010
------
0101左移 Left Shift 操作规则将二进制数的所有位向左移动指定的位数左移时低位补0高位丢弃。 1010 1 10100乘以2n 1 相当于将n乘以2。高速计算乘法左移可以用来快速计算n的2的幂次方倍数。
右移 Right Shift 操作规则将二进制数的所有位向右移动指定的位数右移时高位补符号位有符号数时补1没符号数时补0。 1010 1 0101除以2n 1 相当于将n除以2。高速计算除法右移可以用来快速计算n的2的幂次方除法。
获取某一位的值
n k 1说明n k 将n右移k位然后与1做按位与运算这样可以获取n的第k位数字0或1。
获取n的最后一位1
lowbit(n) n -n说明n -n 用来得到n的最后一位1。例如n 12 (1100) 时lowbit(n) 的结果为 4 (0100)。 -n 是n的二进制补码表示n -n 会保留n的最后一位1并将其他所有位清零。
位运算的常见应用
判断奇偶性 通过 n 1 判断n是否为奇数如果结果是1则n为奇数。 快速计算2的幂 使用 1 k 来计算 2^k。 检查二进制表示中是否只有一个1 n (n - 1) 0 可以检查n是否为2的幂如果n只包含一个1。 统计二进制中1的个数 __builtin_popcount(n) 或 while (n) {n (n - 1);}每次去掉最右边的1。 交换两个数 a ^ b; b ^ a; a ^ b; 可以用异或交换两个数。 清除低位的1 n (n - 1) 会把n的最低位的1清除。 模拟集合 通过位运算可以模拟集合的操作如 set、union、intersection 等。例如n 可以表示一个集合其中第k位表示是否包含元素k。
1.7 离散化
核心作用将数值范围较大的数据映射到一个较小的连续整数范围便于在数组、前缀和、差分、树状数组、线段树等数据结构中操作。
主要解决值域大、数据稀疏的问题结合其他算法实现高效求解如扫描线、差分数组、树状数组和线段树等。
vectorint 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]无法直接操作。通过离散化将所有区间端点压缩到较小范围。 思路 离散化所有区间的端点。用差分数组或扫描线记录区间变化统计覆盖长度。
2. 区间查询与修改
题目有 n 个点每次给区间 [l,r][l, r] 增加一个值 cc并查询某个点的最终值。 分析区间范围过大如 1∼1091 \sim 10^9通过离散化压缩到有限范围。 思路 离散化所有可能的坐标。使用差分数组、树状数组或线段树进行区间操作。
3. 动态求第 K 小值
题目有 n 个操作每次插入一个值或查询当前数据的第 k 小值。 分析可能有很大的值范围如 [1,109][1, 10^9]通过离散化解决大范围权值问题。 思路 离散化所有插入的值。用树状数组或线段树统计权值频次。
4. 区间最大重叠次数
题目给定 n 个区间求区间重叠最多的时间点及重叠次数。 分析时间点范围可能很大需离散化区间端点。 思路 离散化所有区间端点。使用扫描线或差分数组统计每个离散点的重叠次数。
5. 动态逆序对计数
题目给定一个初始数组每次插入一个值实时输出数组的逆序对个数。 分析插入值可能范围过大如 [1,109][1, 10^9]需离散化值域。 思路 离散化所有可能的值。用树状数组或线段树动态维护逆序对。
6. 二维区间问题
题目给定 n 个矩形求哪些矩形有重叠区域或总覆盖面积。 分析矩形坐标范围可能很大需对 x 和 y 坐标分别离散化。 思路 对 x 和 y 轴分别离散化压缩到二维数组。使用二维差分或扫描线处理。
7. 模拟车流/时间段事件
题目给定 n 个车辆的进入和离开时间求某时刻停车场中车辆的数量。 分析时间范围可能很大如 [1,109][1, 10^9]需离散化时间点。 思路 离散化所有进入和离开的时间点。使用差分数组统计每个时间点的车辆变化。
8. 区间众数统计
题目给定一个数组支持动态查询任意区间内的众数。 分析值域较大如 [1,109][1, 10^9]需离散化元素值。 思路 离散化数组中的值。用莫队算法或树状数组分块统计。
具体例题
区间统计问题Leetcode 56 合并区间。动态第 k 小问题Leetcode 315 计算右侧小于当前元素的个数。区间重叠次数AcWing 1240 最大区间重叠。动态逆序对计数Leetcode 493 翻转对。二维差分矩阵AcWing 1226 最大矩形面积。
1.8 区间合并
using PII pairint, int;// 合并区间的函数
void merge(vectorPII segs) {vectorPII 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; // 更新sted seg.second; // 更新ed} else { // 当前区间与前一个区间重叠ed max(ed, seg.second); // 合并区间更新ed}}// 4. 最后一个区间加入结果if (st ! -2e9) res.push_back({st, ed});egs res; // 更新输入数组
}
