倍增法（ST算法）

1.算法描述

算法思想

st算法，适用于RMQ问题（区间最大值），也就是求出一个序列中，数值最大的一项。朴素做法自然是一遍扫描找最大值，但是当题目询问次数很多的时候，就很有可能超时，因此用倍增算法来进行一个优化。

以下是st算法求解RMQ问题的实现：

首先，我们用$f[i][j]$来表示在序列a中，第i位数字以后数$2^j$个数之中的最大值，那么就可以得到$f[i][0]=a[i]$。

接下来进行一个DP的过程：

for (int j = 1; j <= (log2(n)); j++)
    for (int i = 1; i <= n - (1 << j) + 1; i++)
        f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

2.模板

2.1 预处理

// 预处理
void pre_work() {
    for (int i = 1; i <= n; ++i) f[i][0] = a[i];  // 处理长度为1的区间
    int t = log(n) / log(2) + 1;                  // 计算分段数
    for (int j = 1; j < t; ++j)                   // 遍历不同长度的区间
		for (int i = 1; i <= n - (1 << j) + 1; ++i)  // 左边界遍历
			f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);  // 进行dp操作
}

2.2 询问

// 询问区间[l,r]中最值
int ST_query(int l, int r) {
    int k = log(r - l + 1) / log(2);  // 找到l和r间的一个分界点 t
    return max(f[l][k], f[r - (1 << k) + 1][k]);  // 返回[l, t]和[t,r]中最大的那个
}

3.典型例题

洛谷 3865【模板】ST表

题意： 给定一个长度为 N 的数列，和 M 次询问，每次给定[l, r]，求出每一次询问的区间内数字的最大值。

题解： 模板题

代码：

#include <bits/stdc++.h>

using namespace std;

int const N = 1e5 + 10;
int a[N], f[N][32];
int n, m;

// 预处理
void pre_work() {
    for (int i = 1; i <= n; ++i) f[i][0] = a[i];  // 处理长度为1的区间
    int t = log(n) / log(2) + 1;                  // 计算分段数
    for (int j = 1; j < t; ++j)                   // 遍历不同长度的区间
        for (int i = 1; i <= n - (1 << j) + 1; ++i)  // 左边界遍历
            f[i][j] =
                max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);  // 进行dp操作
}

// 询问区间[l,r]中最值
int ST_query(int l, int r) {
    int k = log(r - l + 1) / log(2);  // 找到l和r间的一个分界点 t
    return max(f[l][k],
               f[r - (1 << k) + 1][k]);  // 返回[l, t]和[t,r]中最大的那个
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    pre_work();
    for (int i = 1; i <= m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", ST_query(a, b));
    }
    return 0;
}

CF1335F. Robots on a Grid

题意： 给出一个 n×m 的网格，每个格子有颜色，0 黑 1 白，每个格子还有一个方向，表示这个格子上的机器人会向那个方向走，并保证不会走出格子
摆放机器人，它们同时开始运动，在任意时刻不能有两个机器人在同一个格子里。先最大化机器人个数，如果多种方案机器人个数相等，再最大化摆在黑格子里的机器人数量。$n\ast m<=10^6$

题解： 思维+倍增。有一个比较显然的结论，如果走了n * m步后，两个机器人不在同一个格子里面，那么这两个机器人永远不会相遇。因为n * m步后，这两个机器人已经进入循环了，此时没有相遇的话，那么分别进入永不相遇的循环。那么对于每一个格子，我都可以知道它走n * m后能够到达的最终的格子是哪个，那么我就可以知道最终的格子是哪个机器人走到的，这个使用倍增就可以做到。如果黑色和白色的机器人都走到同一个格子，那么我优先把这个格子给黑色的机器人。

代码：

#include <bits/stdc++.h>

#define int long long
using namespace std;

int const MAXN = 1e6 + 10;
int n, m, T, white[MAXN], black[MAXN], color[MAXN], f[MAXN][21];
string s;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while (T--) {
        cin >> n >> m;
        int size = n * m;
        for (int i = 0; i < size; ++i) black[i] = white[i] = 0;
        for (int i = 0; i < n; ++i) {
            cin >> s;
            for (int j = 0; j < m; ++j) color[i * m + j] = s[j] - '0';
        }
        for (int i = 0; i < n; ++i) {
            cin >> s;
            for (int j = 0; j < m; ++j) {
                int pos = i * m + j;
                if (s[j] == 'R')
                    f[pos][0] = pos + 1;
                else if (s[j] == 'L')
                    f[pos][0] = pos - 1;
                else if (s[j] == 'U')
                    f[pos][0] = pos - m;
                else
                    f[pos][0] = pos + m;
            }
        }
        for (int j = 1; j <= 20; ++j)             // 遍历不同长度的区间
            for (int i = 0; i < size; ++i)        // 左边界遍历
                f[i][j] = f[f[i][j - 1]][j - 1];  // 进行dp操作
        for (int i = 0; i < size; ++i) {
            int to = i;
            for (int j = 20; j >= 0; --j)
                if ((1 << j) & size) to = f[to][j];
            color[i] ? white[to] = 1 : black[to] = 1;
        }
        int res_all = 0, res_black = 0;
        for (int i = 0; i < size; ++i) {
            if (black[i])
                res_all++, res_black++;
            else if (white[i])
                res_all++;
        }
        cout << res_all << " " << res_black << endl;
    }
    return 0;
}