Texcavator 的秘密基地

本文参考【朝夕的ACM笔记】数据结构-ST表 在练习线段树的过程中经常会感叹代码怎么这么长啊啊啊懒标记怎么这么难传啊啊啊 于是在得知有一种代码量远小于线段树的算法时、、、（其实是因为做到了[SCOI2007] 降雨量 就是ST表啦~ 在什么情况下可以用ST表代替线段树呢？ ==不需要区间修改==的==可重复贡献问题== 不需要区间修改很好理解，什么叫做可重复贡献呢？ 我们知道，求一个数组的最大值（比如说长度为10的数组），我们可以先求前六个数的最大值，再求后七个数的最大值，最后求这两个最大值的最大值，虽然这中间有重复的元素，但是对最终的最大值结果不会有影响，这就叫做可重复贡献问题。 但是如果我们要求一个数组中所有元素的和（还是比如说长度为10的数组），我们就不能用前六个元素的和加上后七个元素的和了，这就叫做不可重复贡献问题。 常见的可重复贡献问题包括：求区间最大/小值，区间按位和/或，区间gcd… 怎么构建ST表呢？ ST表是一种基于倍增算法的数据结构 我们设f[i][j]表示区间 $[i, i + 2^j - 1]$ 的最大值，因此f[i][0]表示的就是第 i 个元素本身了 由倍增 ...

参考：https://zhuanlan.zhihu.com/p/574739597 树状数组主要是支持两种操作： 单点修改 区间查询 这两个操作的时间复杂度都是 O(logn)根据前缀和的原理，任意一段区间求和都可以转换成两个前缀和的差，因此区间求和问题转换成求前缀和问题 前提准备：计算 lowbit在此我们定义一个 lowbit(x) ，表示 x 的最末尾一个 1 与这个 1 后面的所有 0 组成的二进制数lowbit(x) 应该怎么实现呢？很简单，这里直接给出结论 lowbit(x) = x & -x还是通过例子来说明 现有二进制数 101100x = 101100反码：010011补码：010100 可以注意到，-x 是 x 末尾的一个 1 到结束的 0 不动，前面全部取反的结果那么 x & -x 就只保留了末尾的 1 和后面的 0因此得到我们的 lowbit 函数：int lowbit(int x){ return x & -x;} 树状数组的含义我们定义原数组为a，用一个数组 tree 维护若干个小区间，tree[i] 表示 ...

因为对位运算实在是太太太太太不熟悉了！所以每次遇到位运算相关的题都要卡好久才能把题目意思转化成容易理解的样子，今晚又被卡了所以一怒之下总结一篇等下次被卡就来翻翻qwq 与 &翻译：同为1取1，只要有0就取0 可以用&来取每一位上的数，如果要判断n的第三位是否为1，就进行 $n$ & $2^{3-1}$ 运算，如果结果为 $2^{3-1}$ ，就说明当前判断的位数上是1，结果是0，就说明当前判断的位数上是0 判断奇偶a & 1 == 1 a为奇数a & 1 == 0 a为偶数 或 | （OR）翻译：有1取1，无1取0 一个数对另一个数进行 | 操作，当前位上是0将不产生任何影响，当前位上是1将会把对应位上变成1 把一个数变成最接近的偶数：a = a | 1 - 1 异或 ^ （XOR）翻译：相同为0，不同为1 一个数和本身进行异或运算得到结果为0 一个数和0进行异或运算得到结果为本身 上两条推出：奇数个相同的数异或运算得到结果为本身，偶数个相同的数异或运算得到结果为0 左移 <<翻译：a << b = a x 2 ...

前缀和一维一维数组中，计算出所有前 n 个数的和，存储在一个单独的数组里，便于后续计算 板子s[0] = 0;for (int i = 1; i <= n; i ++ ){ scanf("%d", &a[i]); s[i] = s[i - 1] + a[i];} s[i] 计算的就是前 i 个数的和当我们需要计算第 l 个数到第 r 个数的和时，只需要用 s[r] - s[l - 1] 即可 二维二维数组中，计算出长为 0 - l， 宽为 0 - r 的矩阵和这个值等于长为 0 - (l - 1) 宽为 0 - r 的矩阵加上 长为 0 - l 宽为 0 - (r - 1) 的矩阵减去 长为 0 - (l - 1) 宽为 0 - (r - 1)的矩阵 最后加上该位置的值 板子for (int i = 1; i <= n; i ++ ){ for (int j = 1; j <= m; j ++ ) { s[i][j] = s[i - 1][j] + s[i][j ...

二分适用于满足二段性的序列，当一个序列中一段满足条件，另一段不满足条件时可以考虑使用二分来加快查找速度 板子// x 是需要查找的数int l = 0, r = n - 1;while (l < r){ int mid = l + r >> 1; if (q[mid] >= x) r = mid; // 符号按需要更改 else l = mid + 1;}return r; 符号判断二分中使用什么符号曾经困扰了我很久，现总结如下：大原则：搞不清就带等号，带等号的时候和字面理解意思相同其中，以下两个式子表示含义相同： >= 会输出满足大于等于条件的第一个数 < 会输出从后往前看不满足小于条件的第一个数 以下两个式子表示含义相同： <= 会输出从后往前看满足小于等于条件的第一个数 > 会输出不满足条件的最后一个数 举个栗子 现有如下序列：1 2 3 4 5 5 5 6 7 8 9 现需查找 “5” —— 当使用 >= 时，找到的是第 1 个 5 当使用 <= 时，找到的是第 3 个 ...