倍增
倍增:
倍增就是翻倍, 它能让线性的处理转化为对数级的处理, 优化了时间复杂度
注: 相当于二分的反方向
原理:
对于一种操作f(x) 通过计算f(x), f^2(x), f^4(x), ...f2^k(x)可以以Log2(n)的速度
求解出f^n(x)
解释:任意整数都可以拆分为若干以2为底的幂项和 以这个作为出发点就可以引发出很多基础算法等等
快速幂: (就是利用了倍增的思想)
快速幂求解的就是a ^ b % p的解
根据倍增不难得出这个公式
Code展示:
using i64 = int64_t;
constexpr i64 mod = 1e9 + 7; // 998244353
i64 power (i64 a, i64 b, i64 p = mod) {
i64 res = 1;
for ( ; b > 0; b >>= 1, a = a * a % p) if (b & 1) res = res * a % p;
return res;
}
龟速乘(快速乘):
推出
Code:
i64 ksc(i64 a, i64 b, i64 mod) {
i64 res = 0;
for (; b; b >>= 1, a = (a << 1) % mod)
if (b & 1) res = (res + a) % mod;
return res;
}
跳跃查询:通过预处理构建一个可以跳跃到更远的节点或区间的表
预处理:在预处理阶段构建一个st表 能过快速查询结果
复杂度:O(log2(n))
博客资料来源:
【算法学习笔记】倍增 - RioTian - 博客园
例题:
P4155 [SCOI2015] 国旗计划
题意:
在一个环上有一些区间, 询问在当前i区间强制选择的前提下 (1 <= i <= n), 用最少区间覆盖整个环的个数
分析题目中的关键信息：
每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含
首先对于环形题目首先想到破环成链, 我们从关键信息下手不难发现, 每个战士的区间都不会被其他战士的区间所覆盖
那么可以得到左区间l, 和右区间r 明显是严格递增的, 其次在每次询问的时候, 选择下一个区间的时候必然是需要右
交集的, 那么我们可以通过排序对l进行排序, 每一次找到选择排外序后尽量选择a[idx].l靠近a[idx].r最右边的区间
在当前图中a[1].[l, r]这个区间我们应当选择a[3].[l, r]这个区间
目前所用的基础算法是一个典型的贪心问题(区间覆盖问题): 通过局部最优推向全局最优(是一个最优策略的贪心问题)
复杂度分析:
在这里光用贪心的写法, 必然是超时的 是因为在每次查询的时候需要从强制选择当前的点继续循环下去
所利用的时间是O(n) 那么n次查询也成了(n ^ 2) 在这个复杂度条件下, 光使用贪心算法是不行的
修改点：
修改点只能在每次询问需要枚举到的线段中做手脚, 那么可以使用倍增预处理, 以O(1)的时间复杂度输出查询的结果
解释为什么使用倍增(理由):
倍增算法不一定需要满足递增关系，但通常用于处理某种结构性或递归性的关系。这种关系可以是递推的、可分解的，而不一定是单纯的递增关系, 那么在这里当前的战士到下一个战士的
路径其实是固定的, 假设当前i的转移对象f[i], 那么f[i]的下一个转移对象是f[f[i]] 它的路径已经是固定好了, 那么问题就变成了加速转移, 那么倍增它来了
原本暴力求解是我一步一步跳, 这里我倍增的跳, 那么我们可以建张表表示st[i][j]表示i战士我直接跳2 ^ j后的下一个战士
指数从大到小枚举, 确保下一次跳跃的战士的覆盖范围小于i + m, 记录ans, "最后再来一次转移使得整个区间能过覆盖i + m", 输出ans + 1即可
递归公式:
关键代码讲解:
区间扩展: (破环成链):
if (a[i].l > a[i].r) a[i].r += m;
a[i + n] = {a[i].l + m, a[i].r + m, a[i].id};
倍增表的构建:
for (int j = 1; (1 << j) <= len; j++) {
for (int i = 1; i <= len; i++) {
st[i][j] = st[st[i][j - 1]][j - 1];
}
}
倍增查询过程: ed = i + m
for (int j = 20; j >= 0; j--) {
int to = st[cbt][j];
if (to && a[to].r < ed) {
cnt += (1 << j);
cbt = to;
}
}
结果输出:
ans[a[i].id] = cnt + 1;
注意: 由于题目很坑 尽量不要在查询的时候输出结果 这是错误的, 因为排完序后的结果是不一样的
Code:
#include
using namespace std;
using i64 = int64_t;
constexpr int N = 2e5 + 5;
struct node {
int l, r, id;
bool operator < (const node &b) const {
return l < b.l;
}
} a[N << 1];
int st[N << 1][25], ans[N] {}, len;
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i].l >> a[i].r;
if (a[i].l > a[i].r) a[i].r += m;
a[i].id = i;
}
sort(a + 1, a + n + 1);
len = n << 1;
for (int i = 1; i <= n; i++) {
a[i + n] = {a[i].l + m, a[i].r + m, a[i].id};
}
int idx = 1;
for (int i = 1; i <= len; i++) {
while (idx <= len && a[idx].l <= a[i].r) idx++;
st[i][0] = idx - 1;
}
for (int j = 1; (1 << j) <= len; j++) {
for (int i = 1; i <= len; i++) {
st[i][j] = st[st[i][j - 1]][j - 1];
}
}
for (int i = 1; i <= n; i++) {
int ed = a[i].l + m, cbt = i, cnt = 1;
for (int j = 20; j >= 0; j--) {
int to = st[cbt][j];
if (to && a[to].r < ed) {
cnt += (1 << j);
cbt = to;
}
}
ans[a[i].id] = cnt + 1;
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << (i == n ? "\n" : " ");
}
}
int main() {
cin.tie(0) -> sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
ST表
介绍ST表 && 什么是可重复贡献问题
ST表: 用于解决 '可重复贡献问题' 的数据结构
'可重复贡献问题': 对于位运算opt, 满足 x opt x = x 那么引申到一个区间
就是可重复贡献问题
举例: 最大值(RMQ问题) max(x, x) = x, 那么它就是一个 '可重复贡献问题', gcd 有
gcd(x, x) = x, 那么gcd也是 '可重复贡献问题', 不够对于区间和就不具备这类性质了,
因此, 只有满足 x opt x这类结合律才满足ST表解决
Code:
//https://github.com/Ckeyliuhi/acm-iters
#include
using i64 = int64_t;
constexpr int N = 1e3 + 5, M = 26;
int st1[N][M], st2[N][M], n, m, a[N], Log[N];
void init () {
Log[0] = -1;
for (int i = 1; i <= n; i++) {
Log[i] = Log[i >> 1] + 1;
}
for (int i = 1; i <= n; i++) {
st1[i][0] = st2[i][0] = a[i];
}
for (int j = 1; j <= Log[n]; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st1[i][j] = std::__gcd(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
}
}
}
int query (int l, int r) {
int idx = Log[r - l + 1];
return std::__gcd(st1[l][idx], st1[r - (1 << idx) + 1][idx]);
}
void solve() {
std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
init ();
while (m--) {
int l, r;
std::cin >> l >> r;
std::cout << query(l, r) << '\n';
}
}
int main() {
std::cin.tie(0) -> sync_with_stdio(false);
int t = 1;
// std::cin >> t;
while (t--) {
solve();
}
return 0;
}