526互联

算法思想

发布时间 2023-04-05 16:09:10作者: Phrvth

\(\mathcal{Part}\) 1. 前提提要

注意：本文为提高组难度的算法思想，主要为前缀和，差分等优化

因为是思想，讲的会比较玄乎，能理解就好

\(\mathcal{Part}\) 2. 双指针

双指针通常解决区间问题

步骤是，确定一个右节点或左节点作为一个参考点，通常取右节点，记为 \(j\)

我们考虑一个刚好符合题目条件的最小节点，记为 \(l\)

双指针有个前提：当右指针往右移动时，左指针不可能往前走

解决步骤：

右指针往右跳，让左指针也往右跳，跳到符合条件为止，这就是题目要求的以 \(r\) 为右端点最长的区间

因为左指针和右指针都只会跳 \(n\) 次，总时间复杂度为 \(\mathcal{O}(n)\)

\(\mathcal{Practice}\) 1.

P1638逛画展

\(\mathcal{Practice}\) 2.

P1102 A-B数对

\(\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\) 清空成 0
  • s.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\) 的正整数次幂之和

\[n=\sum 2^i (i\in\mathbb{N^*}) \]

证明平凡

所以对于每一段区间，我们都可以拆成 \(\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;
}

暂更