ST表

主要用来快速查询静态数据区间最大值

思路

数组$A[i][j]$存储数列$\{a_i\}$中区间$i \in [i, i+2^j)$的最大值
查询时只需要查询$max\{A[i][k], A[j-2^k+1][k]\}$即可，保证$2\times2^k \geq j - i$即可
预处理使用动态规划的思想
位运算勤加括号！
位运算勤加括号！！
位运算勤加括号！！！

P3865 【模板】ST表

题目背景

这是一道ST表经典题——静态区间最大值

请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 $O(1)$。若使用更高时间复杂度算法不保证能通过。

如果您认为您的代码时间复杂度正确但是 TLE，可以尝试使用快速读入：
inline int read()

{

	int x=0,f=1;char ch=getchar();

	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}

	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}

	return x*f;

}
题目描述

给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 $N, M$分别表示数列的长度和询问的个数。

第二行包含 $N$ 个整数（记为 $a_i$），依次表示数列的第 $i$ 项。

接下来 $M$ 行，每行包含两个整数 $l_i, r_i$，表示查询的区间为 $[ l_i, r_i]$

输出格式

输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。

输入输出样例

输入 #1复制
8 8

9 3 1 7 5 6 0 8

1 6

1 5

2 7

2 6

1 8

4 8

3 7

1 8
输出 #1复制
9

9

7

7

9

8

7

9
说明/提示

对于$30\%$的数据，满足：$ 1 \leq N, M \leq 10$

对于$70\%$的数据，满足： $1 \leq N, M \leq {10}^5$

对于$100\%$的数据，满足： $1 \leq N \leq {10}^5, 1 \leq M \leq 2 \times {10}^6, a_i \in [0, {10}^9], 1 \leq l_i \leq r_i \leq N$

完整解答

#include <ctype.h>

#include <cstdio>

#include <algorithm>

#define MAXN 100000

// 这里数组开成ST[25][MAXN]可提速

int Log[MAXN + 10], ST[25][MAXN + 10], N, M, l, r;

// 快速读取

inline int read()

{

	int x = 0, f = 1;char ch = getchar();

	while (!isdigit(ch)) { if (ch == '-') f = -1;ch = getchar(); }

	while (isdigit(ch)) { x = x * 10 + ch - 48;ch = getchar(); }

	return x * f;

}

// 初始化

void init() {

    // log2预处理

	Log[1] = 0;

	for (int i = 2; i <= N + 1; i++) Log[i] = Log[i / 2] + 1;

    // ST表预处理

	for (int i = 1; i <= N; i++) ST[0][i] = read();

	for (int j = 1; (1 << j) <= N; j++)

		for (int i = 1; i + (1 << (j - 1)) <= N; i++)

			ST[j][i] = std::max(ST[j - 1][i], ST[j - 1][i + (1 << (j - 1))]);

}

int main() {

	N = read(); M = read();

	init();

	while (M--) {

		l = read(); r = read();

		int k = Log[r - l + 1];

		printf("%d\n", std::max(ST[k][l], ST[k][r - (1 << k) + 1]));

	}

	return 0;

}

巴特西

[数据结构与算法-13]ST表

ST表

思路

P3865 【模板】ST表

题目背景

题目描述

输入格式

输出格式

输入输出样例

说明/提示

完整解答

最新文章

热门文章