ST算法

这是一道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 个整数（记为 a_iai?），依次表示数列的第 ii 项。

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

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

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

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

对于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 N1≤N≤105,1≤M≤2×106,ai?∈[0,109],1≤li?≤ri?≤N

思路：

首先搞一个二维数组f[i][j]来记录从i这个点往后区间长度为2^j的最大值。ST是很明显的倍增，倍增实质上是dp，那么就要有边界条件和状态转移方程。先找状态转移方程：在区间l,r之间找一个值k，使这个值k满足[l,l+2^k]并[r-2^k+1,r]这两个区间能够覆盖[l,r]，由于最大值不用管区间重不重复，一个100放这里你来一千个1也不管用，所以无所谓重不重复，只要能覆盖就行。那么状态转移方程就自然而然的想到：f[i][j]=max(f[i][i+2^k],f[r-2^k][k])。现在状态转移方程有了，找边界条件即可。发现当j=0时就是它自己。

代码：

#include
#include
#include
#include
#includeusing namespace std;
int n,m;
int f[100100][20];
int a[100010];
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;
}//快读，不用快读会T（题目里都告诉你了，不用白不用） 
void ST_prework()
{
    for(int i=1;i) 
        f[i][0]=a[i];//边界条件，由于f[i][j]的含义是在区间[i,i+2^j-1]中的最大值，那么如果将j=0代入得到的结果就是在区间[i,i]中，这显然就只有它自己一个数，所以可以设为边界条件 
    int t=log(n)/log(2);//对数换底公式，值为log2(n)，是能取到的最大值，因为你不能超过n个数 
    for(int j=1;j)
        for(int i=1;i11;i++)//因为区间长度为 2^j，所以最多取到这个值 
            f[i][j]=max(f[i][j-1],f[i+(11))][j-1]);//状态转移方程（倍增实际上就是dp） 
}
int ST_query(int l,int r)
{
    int k=log(r-l+1)/log(2);//保证k取这个值能够覆盖整个区间 
    return max(f[l][k],f[r-(11][k]);//因为一个区间里是2^k个数，所以是f[r-(1
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i)
        a[i]=read();
    ST_prework();
    while(m--)
    {
        int l,r;
        l=read();
        r=read();
        printf("%d\n",ST_query(l,r));
    }
    return 0;
}

这是一道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 个整数（记为 a_iai?），依次表示数列的第 ii 项。

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

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

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

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

对于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 N1≤N≤105,1≤M≤2×106,ai?∈[0,109],1≤li?≤ri?≤N