倍增的经典题目：扩大区间、st表

1. 扩大区间

P4155 [SCOI2015] 国旗计划例题1：P4155 [SCOI2015] 国旗计划

计算能覆盖整个圆圈的最少区间，题目给定的所有区间互相不包含，按区间左端点排序后，区间的右端点也是单增的。

我们首先需要化圆为线，然后贪心(优化为倍增)选择一个右端点最远的线段，并且该线段的左端点在上个线段的内部。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5+10;
struct seg{int id, l, r;bool operator < (const seg & x) const{return l < x.l;}
}a[N];
int go[N][20]; //倍增 
int n, m, ans[N];
void init() {int nxt = 1;for(int i = 1; i<=n*2; i++) {while(nxt <= n*2 && a[nxt].l <= a[i].r) nxt++;go[i][0] = nxt - 1;}for(int i = 1; (1<<i) <= n; i++) { //最多跳2^n, 不超过n for(int st = 1; st <= n*2; st++) {go[st][i] = go[go[st][i-1]][i-1];}}
}
void getans(int x){int now = x, res = 1; //从第x个战士出发 for(int i = log2(N); i>=0; i--){ //注意二进制是从高位开始枚举 int pos = go[now][i];if(pos && a[pos].r < a[x].l + m) { //跳的那个位置不超过一圈后的自己 res += 1<<i;now = pos;  //就可以跳 }}ans[a[x].id] = res+1;
}
int main() {scanf("%d%d", &n, &m);for(int i = 1; i<=n; i++) {scanf("%d%d", &a[i].l, &a[i].r);a[i].id = i;if(a[i].r < a[i].l) a[i].r += m; //化圆为链 }sort(a+1, a+n+1);for(int i = 1; i<=n; i++){ //每一个线段的终点是自己, 想想a[n]是要绕一圈到a[1]的 a[i+n].id = a[i].id;a[i+n].l = a[i].l + m;a[i+n].r = a[i].r + m;}init();for(int i = 1; i<=n; i++) getans(i);for(int i = 1; i<=n; i++){printf("%d ", ans[i]);}return 0;
}

例题2：2021年中国大学生程序设计竞赛女生专场 B攻防演练

与上面的代码很像，大概原理都一样的

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int pos[30], n, m, dp[N][30];
int main(){scanf("%d%d", &m, &n);string s; cin>>s;s = '#' + s;for(int i = 0; i<=20; i++) dp[n+1][i] = n+1; //需要初始化边界, 因为有的dp会跳到最后 for(int i = 0; i<26; i++) pos[i] = n+1;for(int i = n; i >= 0; i--){ //i = 0也要更新, 因为从l-1开始跳 for(int j = 0; j<m; j++)dp[i][0] = max(dp[i][0], pos[j]);if(i) pos[s[i]-'a'] = i;}for(int j = 1; j <= 20; j ++){ //枚举区间长度 for(int i = 0; i <= n; i++){dp[i][j] = dp[dp[i][j-1]][j-1];//以i开始跳, 跳2^j次后到达的最大位置;  即以i开始跳, 先跳2^(j-1)次, 然后再跳2^(j-1)次  }}int q; scanf("%d", &q);while(q--) {int l, r; scanf("%d%d", &l, &r);int ans = 1, p = l-1;for(int j = 20; j>=0; j--){if(dp[p][j]<=r) {p = dp[p][j];ans += (1<<j);}}printf("%d\n", ans);} return 0;
}

2. 区间最大/最小值，st表

如果元素满足倍增关系，例如快速幂、LCA都可以用到倍增

区间最大值：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10, M = 25;
int dp[N][M];
int main() {int n; scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &dp[i][0]);for(int j = 1; j <= 20; j++){ //首先枚举区间长度 for(int i = 1; i+(1<<j)-1 <= n; i++){ //再枚举起点 dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);}}int q; scanf("%d", &q);while(q--) {int l, r; scanf("%d%d", &l, &r);int k = log2(r-l+1);  //区间长度的指数 printf("%d\n", max(dp[l][k], dp[r-(1<<k)+1][k]));}return 0;
}