P3865 【模板】ST表

Posted Wed Apr 15 2020. 1204 words. 6 min read.
Cover Image

This article was last updated on days ago, the information described in the article may be outdated.

题目

[1]

题目背景

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

请注意最大数据时限只有 0.8s,数据强度不低,请务必保证你的每次查询复杂度为 O(1)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;
}

题目描述

给定一个长度为 NN 的数列,和 MM 次询问,求出每一次询问的区间内数字的最大值。

输入格式

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

第二行包含 NN 个整数(记为 aia_i),依次表示数列的第 ii 项。

接下来 MM 行,每行包含两个整数 li,ril_i, r_i,表示查询的区间为 [li,ri][l_i, r_i]

输出格式

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

输入输出样例

输入 #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%30\% 的数据,满足:1N,M101 \leq N, M \leq 10

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

对于 100%100\% 的数据,满足: 1N105,1M2×106,ai[0,109],1liriN1 \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


思路

ST 表是用于解决 RMQRMQ 问题的数据结构
RMQRMQ ,英文 RangeMaximum/MinimumQueryRange Maximum/Minimum Query 的缩写,即区间最大(最小)值

解决 RMQRMQ 问题有很多种方法,比如:线段树,笛卡尔树,然鹅这些高级的树我都不会啊啊啊,只好用 ST 表了

ST 表基于倍增思想,可以做到 O(nlogn)O(n logn) 的预处理, O(1)O(1) 的查询,但是不支持修改操作。

我们用 MAXi,jMAX_{i,j} 表示从 aia_i 开始 2j2^j 个数的最大值,比如 MAX1,0MAX_{1,0} 表示 a1a_1MAX1,1MAX_{1,1} 表示 max(a1,a2)max(a_1,a_2)

可以看看图片的例子,竖着看,看完一列再看下一列,应该就能理解了(B 站上一个视频里的,个人感觉思想讲的挺好的,可以看完再去 luogu 上看看题解的代码)视频链接

最后查询的时候将查询区间分成两段,比如查询 171\sim7 ,那就分成 141\sim4474\sim7

t=log2(rightleft+1)4=r2t+1t = log_2(right - left + 1)\\ 4=r-2^t+1

最后,MAX[i][j]MAX[i][j] 中,j=log2nj = log_2n

#include <cmath>
#include <cstdio>
#include <algorithm>
#define max std::max //骚一下...

const int maxn = 1e6 + 10;
int n, m, MAX[maxn][20];

inline int read() {
bool flag = 0; int x = 0; char ch = getchar();
while(ch<'0' || ch>'9') {if(ch == '-') flag = 1; ch = getchar();}
while(ch>='0' && ch <= '9') {x *= 10; x += ch - '0'; ch = getchar();}
return flag ? - x : x;
}

void ST() {
n = read(), m = read();
for (int i=1; i<=n; i++)
MAX[i][0] = read();
const int maxLog = (int)log2(n);
for (int j=1; j<=maxLog; j++)
for (int i=1; i<=n-(1<<j)+1; i++)
MAX[i][j] = max(MAX[i][j-1],MAX[i+(1<<(j-1))][j-1]);
}
void Query(int l, int r) {
int t = log2(r - l + 1);
printf("%d\n", max(MAX[l][t], MAX[r-(1<<t)+1][t]));
}

int main() {
ST();
for (int i=0; i<m; i++) {
int l = read(), r = read();
Query(l, r);
}
return 0;
}

P2251

然后再一题 P2251 质量检测
题目大意基本相同,不过这里是求 minmin
查询区间依次是1m1\sim m, 2m+12\sim m+1, 3m+23\sim m+2

#include <cmath>
#include <cstdio>
#include <algorithm>
#define min std::min //倔强

const int maxn = 1e6 + 10;
int n, m, MIN[maxn][21];

inline int read() {
bool flag = 0; int x = 0; char ch = getchar();
while(ch<'0' || ch>'9') {if(ch == '-') flag = 1; ch = getchar();}
while(ch>='0' && ch <= '9') {x *= 10; x += ch - '0'; ch = getchar();}
return flag ? - x : x;
}

void ST() {
n = read(), m = read();
const int maxLog = (int)log2(n);
for (int i=1; i<=n; i++)
MIN[i][0] = read();
for (int j=1; j<=maxLog; j++)
for (int i=1; i<=n-(1<<j)+1; i++)
MIN[i][j] = min(MIN[i][j-1],MIN[i+(1<<(j-1))][j-1]);
}

int main() {
ST();
const int Log2 = log2(m);
for (int i=1; i<=n-m+1; i++)
printf("%d\n", min(MIN[i][Log2], MIN[i+m-(1<<Log2)][Log2]));
return 0;
}


Comments

Unable to load Disqus, please make sure your network can access.