基础算法（排序、二分、精度运算）

排序

快速排序

主要思想

解法

1、暴力

开辟新数组 遍历之后 将小的放在一个数组里 大的放在一个数组里 最后将两个数组合并到总数组里

2、双指针

i在左边 j在右边 二者同时向中间移动 但i的值大于等于x时 就停下 j的值小于等于x时 就停下 两个都停下之后 交换两个的值 之后 两者再次同时向中间移动 然后继续这个过程 直到i到了j的右边（或者说j 到了i 的左边）

模板：

main函数中 第一次调用模板时 传入 0 n-1（也就是两个边界的下标）因为是向函数传入左右边界值以供使用 参数就是 l r

模版就是那个quick_sort函数
第一行是判断边界 如果里面没有数 或者只有一个数 那么直接return

之后选定left为分界点 之后初始化i 和 j的位置

然后在while循环里 进行do … while 循环
第一个do i++；while （q[i] 第二个就是 只要满足 q[j]>x 那么就会让j–

之后再判断（i

最后递归 依次递归左边区间以及右边区间 以 j 为分界点
quick_sort(q,l,j);
quick_sort(q,j+1,r);

(注意 当递归时传入j时 （例如第一个递归的第三个参数）上面的int x后面必须是q【l】 一定不可以是r)

其它细节

这个表示一百万 100 0000 + 10
所以一百万就是 1e6
+10 是因为预留一些空间 防止越界

根据题目的数据范围 来定义数组的大小

归并

主要思想

首先是两个有序的序列数组 从小到大排列 之后两个指针依次指向两个数组的最小值 也就是最左端 然后比较两个指针的值 将较小值放入res数组 然后谁放入了res 谁的指针后移一位 之后 再次比较 直到某个指针到了最后 那么进行完这次比较之后 将另一个没有比完的数组 依次接在res的最后

当两个数相同时 一般是让第一个序列的指针所指的数放入res

快排以及归并的时间复杂度 都是n*log n

解法

模板：

首先传入q 0 n-1 也就是数组 左边界 右边界

之后在merge_sort函数里面

第一行 判断边界

之后确定分界点 使用 l + r / 2 可以写成 l + r >> 1 这样更快一些

紧接着就分成两个数组 递归调用 以mid为分界点 l mid 以及 mid+1 r

之后 开始合并 首先要定义一个k 用来记录tmp数组的下标 之后i指向l j指向mid+1 也就是都指向两个数组的第一个位置
while循环：当i j 都没出去最后时 循环继续 if 选出较小值 放入临时数组tmp
当第一个循环结束 进入第二个循环 这时 已经有其中一个数组比较完了 所以 就判断是谁还有值 将剩下的值拼接到tmp数组后面即可

最终for循环 将tmp数组的数赋值回q数组 因为最后输出的是q数组 如果不想赋值 直接该输出函数是tmp即可

STL - sort

#include

传入两个指针 指向第一个元素以及最后一个元素 用数组名代替首元素指着 之后q+n指向了最后一个元素

总结时间效率

快速排序 归并排序 STL-sort 三者时间差不多

二分

作用

二分，就是对于一组单调的数据，两边的性质不同，二分可以找到某一边性质的最值，
如果找红色区间，则会找到满足红色性质的最大值（如果是红色区间，mid =( l + r + 1) >> 1）
如果找绿色区间，则会找到满足绿色性质的最小值（绿色区间则正常，mid = (l + r) >> 1）

注意点

最后 L == R 跳出循环，注意，最后有用的不是在循环中定义的那个mid，而是L R 或者num[L] num[R]

整数二分

主要思想

图中两个指针所指的点 可以认为是两个目标点 左边是红色区间边界点 右边是黄色区间的边界点
假如要找红色的那个点 那么就是第一种情况 首先让mid = r + l >> 1
之后 看mid是否满足在红色区间 如果在 那么目标值红点在mid右边 所以mid左边可以丢掉 但是mid不能丢掉 因为mid在有效区间内 所以 L = mid

如果mid不满足在红色区间 那么目标值在mid左边 并且mid在绿色区间 不可能取到目标值 所以直接丢掉mid右边以及mid r=mid-1

然后这个就是下面“解法一栏”的第二个模板 看到 L=mid的更新 就回过头把mid改成 r+l +1 >> 1

假如要找绿色区间边界点 简称绿点 也就是把绿点当做目标值 首先让mid= r + l >> 1
之后 看mid是否满足绿色区间 如果满足 那么目标值在mid左边 那么 更新r=mid
else mid在红色区间 目标值在mid右边 更新 l = mid +1

解法

模板：

思考过程
循环条件一定是 l < r 再继续循环，这样的话，一旦l == r ，那么就说明找到了输出 l或r，或者他们的对应位置
首先 先写mid = l + r >> 1
之后写check（）函数 或者直接判断也可以 总之要有一个判断mid在目标值左还是右（注意只是检查性质，两边性质对立即可，而具体怎么检查，要看题意，一般好检查）
之后看满足第一种情况还是第二种
如果是更新了 l=mid 那么回过头来修改mid 在mid的分子上 + 1
如果是更新了 r=mid 那么就无需修改mid

举例：

这里让找每个查询元素的起始位置以及终止位置 那么 我们这里只看某一个查询元素即可

起始位置

首先来找起始位置：
对于一个x 假设我们定性质为 >=x
这样就符合找绿点的情况

最外层while是指m个查询 所以循环体里就是一个查询的代码
目标值用一个变量表示 因为一般都是程序来输入目标值 我们来查找

首先 初始化 l 和 r 的位置 分别是 0 n-1
之后while（l 在小循环里 首先定义mid
之后因为要查询绿点 所以 q[mid] >= x
如果为真 那么 r = mid
else l = mid + 1

结束位置

之后找右边坐标 可以理解为右边界


这里插播一下无解的情况 如果最后的结果不是x （如果不是 那么q【l】的值就是>x的第一个值 ） 那么就是无解 直接返回无解的值

这里就是找红点的情况
首先check就是q【mid】<=x 更新 l = mid
else r = mid - 1
这里看到更新的是 l = mid
所以回去修改mid = r + l + 1 >> 1

最后输出 l 其实输出 l 还是 r 都一样 因为 循环最后跳出的条件就是 l = r

例题2

主要是找到一个数的位置（下标），该数位置左右两边有不同的性质
也就是最终 会得到 num[l] = num[r] =目标值x
所以最后

会拿到x的下标
至于x的值是不是已知的 是不确定的

（当x已知时 可以拿x当参考点 会比较舒服
但是有时候x未知 那么就要重新寻找新的参考点 该点左右两边分别有对立的性质 并且该点的性质对应着以x为参考点时的性质 也就是同一个性质 换了一个已知点或者说好定位的点来体现 实质上还是在找x左右两边的性质）

以下是x未知时 利用已知点来表示x左右的性质


由于要找最小值 但是最小值未知 所以采取性质对应的方法 我们进行二分的时候 要先定义出来l=0 r=size（）-1
所以左右两个端点是很容易拿到的 同时该题具有单调性质 也就是最小值左边的数 一定大于nums[r] 最小值右边的数 一定小于nums[r]

所以 性质对应：
nums[mid]>=x -> nums[mid] < nums[r] 对应查找绿点
nums[mid]<=x -> nums[mid] > nums[r] 对应查找红点

浮点数二分

解法

这里无需考虑边界问题 当设定的条件是 mid在目标值右边 更新r = mid
否则 更新 l = mid

循环条件：
如果要求输出六位小数 那么循环条件是 r - l > 1e-8
如果要求输出四位小数 那么循环条件是 r - l > 1e-6

高精度

加法

主要思想

大写字母表示一个大数 小写字母表示一个小数 题型有四种 大数与大数的加减 大数与小数的乘除
上面所写的10的6次方 意思是 len（A） 也就是一个数的长度

拆分思想：


首先用一个数组来存储这个大数 小位在前面 大位在后面 所以就是上面那种情况 数组下标从0到8所存储的值依次是：9 8 7 6 5 4 3 2 1
当然 数组可以用vector容器来代替

之后第二步 就是模拟人工算法 定义一个进位数 t A0+B0+t 取模 然后判断 是否进1 等等

解法

模板：

首先 auto的功能是 可以自动推算后面的数据是什么类型 这里可以推断出C是vector 类型
同时也可以看到vector读取数据的时候 可以用下标来读取 但是压入数据必须用push_back

首先 在main函数中 因为是大数 所以要用string来存储数据
之后定义两个vector 容器

之后从string的后面开始读入数据 而向容器中压入数据时 要减去偏移量“ ‘0’ ” 这样得到的才是数字

在add（A，B）中
首先传参数用引用 提高效率

之后定义t 用来进位
for循环 i从0开始 直到都遍历完 所以条件是 i < A.size() || i < B.size();
循环体中 如果A还有数 那么 t += A[i]
如果B还有数 那么 t + = B[i]
这时已经完成了A+B +t
就可以向容器C中压入数据了 因为初始t等于0 每次都是 t = t + …
之后更新t t /= 10

最后判断t是否有值 有值则在最后（也就是最高位）补一个1
最后返回C

减法

主要思想

首先要保证是 较大值减较小值 如果反了 就反过来传参 最后加个负号即可

而每一位的运算 都是A[i]-B[i]-t t记录着借位的情况 如果有借位 那么 t = 1
而对于A[i]-B[i]-t 如果大于0 那么直接运算即可 如果小于0 那么要从高位借一个10

解法

模板：

首先定义一个是否A >=B的函数

因为已经保证了A大于B 所以 for循环里只需要考虑 i 和加法一样 都是将值加到t里 借助t来运算 首先是t = A[i] - t
然后当B还有位时 t=t - B[i]
最后直接压入（t+10）%10 因为该语句集成了两种情况 如下：

也就是集成了借位与不借位 无论借位与否 这样的值绝对正确
最后判断t是否为负数 如果为负数 那么就是借位了 那么下一轮循环中 t = 1 esle t = 0

最后一个while循环：去掉前面的0
（且注意，while循环里是C.size() > 1 ,因为考虑到当C.size() == 1 && C.back() == 0时，答案一定是一个一位数：0，此时0就是答案，别除去）

这里在传入参数之前 先判断是否有A> =B
对于不同的情况 采取不同的措施
注意 加负号时 直接在输出语句前多输出一个负号即可

乘法

主要思想

压入时 压入（A * b + t ）%10

同时更新进位： t=（A * b + t ）/10

解法

模板

循环条件多了一个 t 不为0
循环条件：如果i 这时循环里面就要判断 A还有位数时 t += A[i] * b;

之后压入 t % 10
更新 t /=10

除法

主要思想

主要就是拿到余数进行操作
拿到余数之后 先将余数*10 之后加上A[i] 也就是第一次更新余数
之后压入 r/b 也就是对除数取整
然后二次更新余数 r = r % b 对除数取余 然后更新余数r

因为这里的C容器是反着存放数据的 所以最后要将C reverse一下 传入首尾迭代器
然后还要去除前导0 使用while循环

前缀和

一维

主要思想

实际上 就是求和思想 求Si 的前 i 项和 注意没有a0 a的下标从1开始
把S[i]用用一个循环求出来 并且存入一个数组中
之后利用S数组进行运算即可

同时要注意S[0] = 0
这样方便边界的处理 以及公式的统一 当求某个区间是从1开始的时候 S[0]=0 就派上了用场

解法+例子

第二个for循环 就是在构建新数组 S

二维

主要思想

Sij表示点ij的左上角数据的和
所以Sx1y1=Sx2y2-Sx2y1-1-Sx1-1y2+Sx1-1 y1-1
因为是整数 所以不能边界点不能重合 所以可以看到有-1

而Sij的推导是：

例子+题解

第二个for循环就是在构造S数组

差分

主要思想

给出了原数组A
我们要构造原数组A的的差分数组B 使得B数组的前缀和是A数组

作用：
比如说要求A数组某段都+c之后，变化之后，输出A序列的各个值

如果正常算 需要将这一段每个值都+c

但如果用差分 让bl+c即可 这样从l到r都自动加上了c 同时br+1 -c 保证r后面的A元素不受影响
图形化：

时间复杂度：

从o（n）变为o（1）

oi

接下来是构造B数组的思想

首先假设A数组都是0
这样的话差分数组B的元素也都是0

但是题目会给出A的元素值 也就是A在题目中不是0 所以可以认为对A数组进行了n次的插入操作 每次操作的区间是【1，1】【2，2】…【n，n】（之所以使用insert来构造B，是因为这样可以一函数两用，即用他来构造初始的B，也用来进行后续核心的算法操作）
（insert对外接口可以解释为是对a的某个区间插入加上某个数，而内核是对b数组的操作，所以有对某个相同断点的区间加入值，可以解释为 对a数组进行二次复现 但实际效果是构造出了b，或者说，建立了b与a的联系）
依次插入 a1 a2 a3…an

解法+例子

首先要注意这里的for循环都是从1开始 小于等于n结束 因为前缀和里的下标都是从1到n
首先for循环输入a[i] 但是现在默认A中的元素全是0
然后向B中插入每个区间的a[i]值 这样就构造出了a[i]（A）的差分数组b[i]（B）
这样 B数组就被构造完成了

插入insert函数中 是向B数组中插入值 同时在某个位置打补丁 这样 对应的A也就有了+c的效果

接着在main函数中 接着是一个while循环 有m个查询
依次按照题目要求进行insert（l，r，c）
这样B数组被按照题目要求进行加值 m个区间都被加值

之后一个for循环 是将B数组进行递归相加 这样B数组就变成了A数组（因为B和A是逻辑上的关系，实际代码上A和B暂未建立直接联系，但是因为有逻辑关系，所以这里想办法用B来表示A，用到的办法就是上面的前缀和，此时B已经构造好了，所以使用前缀和就计算出了最终的A）
最后输出B数组即可
补充：
第30行可以用如下图正经的前缀和来代替

双指针算法

类型+一般写法+核心思想（作用）

双指针算法 就是在朴素算法的基础上 找到其中一个非遍历指针的一些单调的性质

如本题 j指针就是非遍历指针 该指针的作用是用来探索举例 i 指针左边符合题意的最远的位置
j只能向右移动 因为是连续序列 且有重复的数 所以 如果出现j倒退还能符合题意 那么就不符合 j 的旧位置是最左这个特点 出现了矛盾 所以 j只能随着 i 在某些情况下向右走
这个就是j的单调性质 所以就会有在 i 的循环里 j++ 循环条件是 j 单调的限制条件
因为 j 只能跟着 i 单方向走，
每次对于每个 i ，j 只能向着靠近 i 的方向走且不会超过 i ，所以是 i 每走一步，j 只能走一个片段，当 i 走完所有的n之后，j 最多走了n步，也是走到跟 i 重合，所以 i 和 j 加起来最多 2n个状态，所以时间复杂度是o（n），
换句话说，对于每次 i ，j 的状态都会确定，且是单调确定的，所以循环的只有 i ，故是o（n）的时间复杂度

而朴素算法是对于每个 i 都有 n个 j 遍历，所以最多有 n * n 个状态，所以时间复杂度就是o（n的平方）

上图中 右边的check 函数 具体是 j 与 i之间没有重复元素 这个也是限制指针且满足题意的性质

例子

首先a[n]是用来读取数据 s[n]是用来判断区间是否有重复数据 s[n] 用来存放当前a[i]的数量 （当某个s[a[i]]大于1的时候 就说明j i 区间内有重复元素了）刚开始 是1 2 这时 s[1] s[2]的值都是1 还不足以进入while循环 j也没有移动 说明目前来说 i 和 j 之间没有重复元素
之后 当 i 指向第三个元素的时候 s[2]变成了2 也就是2出现了两次 所以进入了while循环 因为这时已经有了重复元素 所以while循环里 要进行 j 的移动 同时每次移动要进行s[ a[j] ]–的操作再移动j 因为这样才会把 j 移动之后的左边的数排除（因为 j 要移动了，所以移动之后左边的数就不能再计入了，已经被舍弃了），而且还要排除那个重复元素 一旦重复元素被排除 那么s[a[i]]就会不再大于1 那么循环停止 这时 j 和 i之间就没有重复元素了

要注意：要在for循环中取max，因为for循环会把所有的情况枚举出来，而最终的结果不一定是max，我们要在每次循环时去手动取max

位运算

& 、| 、^ 、>> 、 <<介绍

x & y

将x、y都转为二进制，之后对比每一位，两个都为1，则为1，最后将结果转为十进制

x | y

将x、y都转为二进制，之后对比每一位，如果有一个为1，则为1，最后将结果转为十进制

x ^ y

将x、y都转为二进制，之后对比每一位，如果两位不一样，则为1，最后将结果转为十进制

x >> y

将x转为二进制，之后将其向右移动y位，移出去的直接舍弃，最后将结果转为十进制
ps，如果x >> 1，则表示 x整除2

x << y

将x转为二进制，之后将其向左移动y位，多出来的位补0，最后将结果转为十进制
ps，如果x<<1，则表示 x乘2

n>>k & 1

主要思想

该算法就是可以将二进制表示法某一位输出

第一步是 n>>k 就是把n的二进制表示法的第k位的数 移动到最后一位 也就是最右边的个位 （注意第k位的定义，最右边第一个是第0位，k可以取到0）
而第二步 就是查看位运算之后在二进制下，个位是几 就是x&1（而不是% 1，不要混淆）

例子

输出10的二进制表示法

依次取到最高位 然后输出 就会输出整个二进制表示法，从最高位开始位运算，由此可以看出，位移运算是拷贝运算，而不是引用运算，即不会影响到原数据

lowbit

思想

定义一个函数lowbit 返回一个十进制数的二进制表示法的最右边的一个1以及后面的0

他的实质是利用一个数在计算机中的二进制表示 然后利用二进制的反码+1 与原码取&的操作 如上图 就可以取到最右边的一个1
补充：&的操作就是，观察两个二进制表示法的数对应位，两个都是1才是1，否则为0。
所以取反之后都是不一致的，+1的话，会在取反之后的最右边的0位置变成1，对应的就是原码中的1的位置，这样只有该位置是一致的都是1，其他位置都不一致，那么将x 与 （~x+1）进行取&的话，就可以把该位置的 1 拿到，以及这个 1 后面的0，对应到代码上是拿到这样的二进制之后转化为10进制输出的（如果要输出的话）
而取反+1，正好就是x的补码，即x的负数的计算方法，所以~x+1，就是-x

例子+模板

首先定义出lowbit 直接return x& -x

然后在n个查询中
输入x 当x不为0时 就继续循环
每次x -= lowbit（x）
因为二进制上缺失某些位，并在这些位上补0的话，在十进制上表现为减去这些位的十进制数
（同时我们也看到，lowbit是拷贝运算，不是引用运算，lowbit（x）这一步并不会改变x，所以才会有x = x - lowbit（x），手动改变原数据）
同时记录次数 这样该次数就是二进制表示法中1的个数

异或

性质

异或有三个性质，如上所示，
1.任何数与0做异或，结果仍然是自身
2.任何数与自己异或，结果是0
3.异或满足交换律和结合律
所以，可以用来进行类似于消消乐的操作，因为相同会相消，且消为0，而0参与异或操作时，不影响其他不为0的项，所以，可以用于处理在所有双数中锁定单数

例题+题解

写异或操作时，类比乘法操作，只不过乘法操作要将res初始化为1，这里初始化为0，因为0在异或里相当于幺元

离散化

主要思想

首先先去重 然后将数组中元素的值x进行离散化 也就是将其按照相对位置映射到下标为1 2 3 …n等自然数的数组里

适用于值域很大 但是研究的值很少 很稀疏
模板：

前三行是利用c++的STL进行去重

然后二分进行查找x的下标

然后映射到1 2 3 … n

例子

NO7.重定义pair 为PII
NO9.准备开一个30万大小的数组，（因为题目中待处理的坐标的最大规模是30万）
之后 a数组用来存离散化之后的坐标，s数组用来预处理前缀和
之后 alls容器用来存储将要被离散化的一些原始坐标
add容器用来存储“添加操作”的数据，query用来存储“查询操作”的坐标（二者的元素都是PII）
然后 main函数里：
输入n 和 m
之后for循环n次，每次输入x和c，并将其作为一个pair绑定起来存入add
之后，将x加到alls中
之后for循环m次，输入 l 和 r
加到query容器里，注意这里代码有误，应该用花括号将l 和 r 括起来
之后将 l 和 r 加到alls中

至此，所有的数据已经加到了所有的容器中

数据加入了之后，我们开始离散化的操作
第一，先去重，首先将alls排序，然后进行去重

之后，范围for循环，拿到每个add的元素之后，将pair的first进行离散化，并使用离散化后的坐标，将数据加到a数组里
之后预处理前缀和，注意 i 从1 开始然后小于等于alls.size()，从1开始进行前缀和预处理

最后处理询问，将询问中的原坐标进行离散化之后，利用a数组的前缀和查询（即s数组）

注意：要在前面加上离散化函数find

实际上就是二分，是使用绿色部分的二分，
对于check条件，因为在使用find之前，我们对alls的数据进行了sort和去重，所以，这里就是坐标大小的比较
这里x就是一些原始坐标，这些坐标可能会特别的离散，也就是值有大有小，且分散化严重，然后我们利用alls的数组下标进行离散化，因为下标肯定是从0开始的连续的较小值，所以，输入一个大的原始坐标数据，我们返回其在alls数组中的下标+1，这样就把分散的、数值大的坐标，离散化为了连续的数值小的坐标，而之所以+1，是为了离散化后的坐标从1开始，因为我们后续要进行前缀和。当我们不进行前缀和时，可以直接返回r

区间合并

主要思想

将有交集的区间进行合并 求出并集 算作一个答案


首先对区间左端点进行排序
我们首先维护一个区间 然后扫描后面的区间
所维护的区间 与 后面的区间有三种关系

第一种 那么就修改所维护的区间 修改为并集区间
第二种 仍然是修改为并集区间
第三种 无交集 那么说明 该区间（包括该区间）往后都与所维护的区间没关系了
那么所维护的区间就是答案了 就可以拿走了

最后更新所维护的区间为第三种所扫描出来的区间

例子+题解

首先 对于区间 用pair来定义

且存放到一个vecor容器中

然后对pair排序 默认会对first排序从小到大 其次对second从小到大排序

然后初始化维护的区间的端点值 用两个负无穷初始化 可以根据数据的范围 适当放大即可

然后遍历每个Pari
if ed 再判断st是否为初始值 不是的话 就是答案
接着要更新st 和 ed 更新成当前扫描到的区间
else 那么就是第一第二种情况
直接更新ed=max（ed , seg.second）
那么一直更新总会满足第三种情况 当满足第三种情况时 就会在上面进行压入了

最后来个if一方面是为了防止空输入，另一方面是最后会剩下一个区间 把他也加入到答案中
最后把res 放入 segs 通过引用返回

通过引用返回回来 对segs进行输出