luogu 3865 st表模板

luogu 3865 st表模板

​​ 日常复习模板x

st表（稀疏表）是解决RMQ问题一个常用的方法（写起来方便跑的也不慢.

主要思想应该是倍增以及区间dpdpdp . 以模板里求区间最大值为例，f[i][j]f[i][j]f[i][j] 表示区间 [i,i+2j{2^j}2​j​​-1] 的答案. 考虑把区间分成两部分，于是dp[i][j]dp[i][j]dp[i][j] =max(dp[i][j−1]dp[i][j-1]dp[i][j−1],dp[i+2j−1][j−1]dp[i+2^{j-1}][j-1]dp[i+2​j−1​​][j−1]). dp[i][0]=a[i]dp[i][0]=a[i]dp[i][0]=a[i]. 查询区间 [l,r][l,r][l,r] 时只要找一个k=floor(log2(r−l+1))k=floor(log_2 (r-l+1))k=floor(log​2​​(r−l+1))，然后对f[l][k]f[l][k]f[l][k] 和 f[r−2k+1][k]f[r-2^k+1][k]f[r−2​k​​+1][k] 取最值就好啦，这两个表示的恰好就是区间 [l,l+2k−1][l,l+2^k-1][l,l+2​k​​−1] 和 [r−2k+1,r][r-2^k+1,r][r−2​k​​+1,r]. 预处理O(nlogn)O(nlogn)O(nlogn) ，单次查询O(1)O(1)O(1) ，总复杂度O(nlogn+m)O(nlogn+m)O(nlogn+m).

题目背景

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

请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1)O(1) O(1)

题目描述

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

输入输出格式

输入格式：

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

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

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

输出格式：

输出包含 MM 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≤N,M≤10 1 \leq N, M \leq 10 1≤N,M≤10

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

对于100%的数据，满足： 1≤N≤105,1≤M≤106,ai∈[0,109],1≤li≤ri≤N 1 \leq N \leq {10}^5, 1 \leq M \leq {10}^6, a_i \in [0, {10}^9], 1 \leq l_i \leq r_i \leq N 1≤N≤105,1≤M≤106,ai∈[0,109],1≤li≤ri≤N

#include#define N 110000inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}inline int max(int x,int y){ return x>y?x:y;}int Log[N],f[N][20],n,m;inline int query(int x,int y){ int k=Log[y-x+1]; return max(f[x][k],f[y-(1<>1]+1; //for (int i=1;i<=n;++i) printf("%d,Log[i]); for (int j=1;(1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。