\(\mathcal{Part}\) 1. 前提提要
注意：本文为提高组难度的算法思想，主要为前缀和，差分等优化
因为是思想，讲的会比较玄乎，能理解就好
\(\mathcal{Part}\) 2. 双指针
双指针通常解决区间问题
步骤是，确定一个右节点或左节点作为一个参考点，通常取右节点，记为 \(j\)
我们考虑一个刚好符合题目条件的最小节点，记为 \(l\)
双指针有个前提：当右指针往右移动时，左指针不可能往前走
解决步骤：
右指针往右跳，让左指针也往右跳，跳到符合条件为止，这就是题目要求的以 \(r\) 为右端点最长的区间
因为左指针和右指针都只会跳 \(n\) 次，总时间复杂度为 \(\mathcal{O}(n)\)
\(\mathcal{Practice}\) 1.
\(\mathcal{Practice}\) 2.
\(\mathcal{Part}\) 3. 前缀和
一维前缀和
我们有一个序列 \(A\)，我们要进行一下操作
- \(\mathcal{O}(n)\) 地预处理
- 给定一个 \(l\) 和 \(r\)，求 \(\sum_{l\le i\le r} A_i\)，时间复杂度为 \(\mathcal{O}(1)\)
我们记一个数组 \(B\) 满足
\[B_i=\sum_{1\le j\le i} A_j \]预处理 \(B\) 数组，时间复杂度为 \(\mathcal{O}(n)\)
我们要查询 \([l,r]\) 的值，也就是 \(\sum_{l\le i\le r} A_i\)，经过简单数学推导，如下
\[\begin{aligned} \sum_{l\le i\le r}A_i&=\sum_{1\le j\le r}A_j - \sum_{1\le k <l}A_k\\ &=B_r-B_{l-1} \end{aligned} \]通俗点来说，就是 \([l,r]\) 的值等于 \(B_r-B_{l-1}\)
前缀和在众多领域起着重大作用，以代码量小和快著称
弊端是：不能动态修改
二维前缀和
给定一个二维序列，记为 \(A\)，现要支持
- 给定两点 \((l_1,r_1)\) 和 \((l_2,r_2)\)，求以两点为矩形端点的矩形，里面所有数之和
记一个二维数组 \(B_{i,j}\) 为 \((1,1)\) 到 \((i,j)\) 的数之和
初始化 \(B_{i,j}=B_{i-1,j}+B_{i,j-1}-B_{i-1,j-1}+A_{ij}\)
证明平凡，自己画图
则两点 \((l_1,r_1)\) 和 \((l_2,r_2)\)，求以两点为矩形端点的矩形，里面所有数之和就为：
\[B_{l2,r2}-B_{l1-1,r2}-B_{l2,r1-1}+B_{l1-1,r2-1} \]推导过程平凡，请自己画图证明
多维前缀和
类比容斥原理
\(\mathcal{Practice}\)
见题单
\(\mathcal{Part}\) 4. 差分
一维差分
现有一个序列 \(A\)，先要支持
- 动态修改 \([l,r]\) 的值
- \(O(n)\) 打印 \(A\) 序列的每个数
记一个数组 \(B\) 满足
\[B_i=A_i-A_{i-1} \]我们看看 \(A_i\) 等与什么
\[\sum_{1\le j \le i}B_j=\sum_{1\le j\le i}A_j-A_{j-1}=A_i \]也就是说，差分的前缀和等于原数组，简单的想，前缀和的差分等于差分
这三者就有机的连在一起了
接下来看怎么修改，记修改的数为 \(k\)
- 当 \(i=l\) 时，\(B_i'=(A_i+k)-A_{i-1}=B_i+k\)
- 当 \(i = r+1\) 时， \(B_i'=(A_{r+1}-(A_{r}+k))=B_i-k\)
- 当 \(i\in (l,r]\) 时，\(B_i'=(A_i+k)-(A_{i-1}+k)=B_i\)
通俗点说，就是修改 \([l,r]\) 的值时，只需要修改 \(B_l\) 和 \(B_{r+1}\) 的值即可
时间复杂度为：\(\mathcal{O}(1)\)
二维差分
类比 \(S_{i,j}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+A_{ij}\)
因为 \(B\) 的前缀和为 \(A\)，则用 \(A\) 替代 \(S\)，\(B\) 替代 \(A\) 则
\[A_{i,j}=A_{i-1,j}+A_{i,j-1}-A_{i-1,j-1}+B_{i,j}\\ B_{ij}=A_{i,j}-A_{i-1,j}-A_{i,j-1}+A_{i-1,j-1} \]这就是二维差分的初始化了
我们考虑修改 \((u,v)\) 到 \((n,n)\) 的差分
- 当 \((i,j) = (u,v)\) 时，\(B'_{i,j}=(A_{i,j}+w)-A_{i-1,j}-A_{i,j-1}+A_{i-1,j-1}=B_{i,j}+w\)
可以证明，其他位置的差分值不变
可以推导 \((u,v)\) 到 \((x,y)\) 的差分值为
\[B_{u,v}+w,B_{u,y+1}-w,B_{x+1,v}-w,B_{x+1,y+1}+w \]证明平凡，类似后缀和
多维差分
和二维差分的推导过程一样
\(\mathcal{Practice}\)
见题单
\(\mathcal{Part}\) 5.离散化
我们要将一个值域为 \((-\infty,\infty)\) 的数映射到 \((0,n]\) 之中
怎么做到呢？
我们知道，映射有个性质
- 每个数的大小关系不变
想到什么？排名是不是可以完美做到这一点？
所以，我们第一步是将原数组去重排序+排序
排序用 sort 人尽皆知，去重用什么呢？
使用 unique 函数，使用格式： unique(a.begin(),a.end())这里 a.begin(),a.end() 分别指数组的头指针和尾指针，普通数组用 a+1,a+1+n
- 注意一点：该函数的返回值是不属于去重数组的第一个地址，比如有个数组长度为 \(n\) ，去重数组长度为 \(k\) ，他的返回值就是 \(a_{k+1}\)的地址。
根据上面几点，我们可以推出公式。
k=unique(a+1,a+1+n)-(a+1)
这样我们就可以求出去重数组的长度了。
第二步，我们求排名
设这个数为 \(A_i\)，\(B\) 数组的排名为 \(k\)，则他在 \(A\) 数组的排名为 \(k\)
那怎么找 \(i\) 呢？这里使用一个函数：
lower_bound(a+1,a+1+n,x) 他返回的是第一个大于等于 \(x\) 的元素的地址，注意：必须有序。
于是，我们可以推出公式：
rk[i] = lower_bound(b + 1, b + 1 + k, a[i]) - b;
到此结束
因为 \(rk_i\) 存的是第 \(a_i\) 在 \(b\) 数组的下标，则
\[B_{rk_i}=A_i \]\(\mathcal{Practice}\)
见题单
\(\mathcal{Part}\) 6. 位运算
基本位运算
- 按位与：\(x\&y\)，把两数的对应位做逻辑与
- 按位或：\(x|y\)，把两位的对应位做逻辑或
- 按位异或：\(x\oplus y\)，把两位对应位做逻辑异或
- 按位取反：\(!x\)，把 \(x\) 的每一位取逻辑非
- 左移：\(x<<y\)，把 \(x\) 的整体向左移动 \(y\) 位，高位抹去，低位补0，（\(x<<y=x*2^{y-1}\)）
- 右移：\(x>>y\)，把 \(x\) 的整体向右移动 \(y\) 位，低位抹去，高位补0，（\(x>>y=\cfrac{x}{2^{y-1}}\)）（向下取整）
单点修改：
- 将第 \(i\) 位修改为 \(1\)：
x |= 1<<(i-1) - 保证第 \(i\) 位为 \(1\)，修改为 \(0\)：
x^=1<<(i-1)
注意：\(<<\) 或 \(>>\) 的优先级比 \(-\) 低，则：\(1<<(i-1)=1<<i-1\)
求两个集合的交集，并集和对称差
可以把两个集合看成一个二进制数，则
\(x_i=0\) 表示 \(i\) 不在集合中，反之同理
两个二进制的与，或，异或可以达到需要效果
神器！\(bitset\)
用二进制表示集合时，普通的变量存不下这么大的二进制，我们可以使用 \(bitset\) 创建一个超长二进制
支持：所有位运算操作也支持修改这个串的某一位
时间复杂度为：\(\mathcal{O}(\cfrac{n}{w})\)，\(w\) 通常取 \(64\)
基本用法：
bitset<N> s表示创建一个二进制数s.set(i,0/1)表示在第 \(i\) 位设置成 \(0/1\)s.test(i)返回第 \(i\) 位的值s.count()返回 1 的数量s.reset()把 \(s\) 清空成 0s.flip()对二进制取反- 可以直接进行逻辑运算
注意：声明 \(bitset\) 时，\(N\) 必须是常量（CE不关我事（doge.
\(\mathcal{Practice}\)
见题单
\(\mathcal{Part}\) 7. 单调数据结构
单调栈
单调栈维护的是一个栈，里面的元素单调递增或单调递减
用于找后缀最大值。
定义：当 \(i\) 为后缀最大值时，当且仅当：对于所有的 \(i<j\le|A|\)，都有 \(A_i>A_j\)
因为栈内数据单调递减，所以对于一个在栈内的元素 \(A_i\)，他后面没有比他大的数（不然就被弹出了
所以留在栈内的都是后缀最大值
时间复杂度为：\(\mathcal{O}(n)\)
单调队列
单调队列维护的是一个队列，只不过里面的数的下标都严格在一个区间里
比你小的人都打不过，你应该出队
被单调队列了
$ Practice$
题比较难，所以我写了几篇题解，自己去看
\(\mathcal{P}art\) 8.倍增
倍增基本概念
我们先来考虑一个引论
- 任何一个 \(x\in \mathbb{N^*}\)，都可以拆成若干个 \(2\) 的正整数次幂之和
证明平凡
所以对于每一段区间，我们都可以拆成 \(\log n\) 个区间
倍增快速幂
我们要求 \(x^y \mod p\) 的值
\(x,y\le10^9\)
怎么办呢？
我们考虑使用倍增的思路：
\[x^y=(x^2)^{\frac{y}{2}} \]这里需要进行奇偶性判断，如果是奇数，则直接乘进答案中即可
时间复杂度为：\(\mathcal{O}(\log x)\)
\(\mathcal{Code}\)
typedef long long ll;
ll qpow(ll d, ll b, ll Mod) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * d % Mod;
d >>= 1; b = b * b % Mod;
}
return ans;
}
暂更
标签：le,思想,sum,差分,算法,数组,mathcal,指针 From： https://www.cnblogs.com/Phrvth/p/17289620.html