锐客网

  1. 首页 > it技术 > >

st表模板

st表 【st表模板】查询区间最值
预处理O(nlogn)
查询O(1)
f(a,b)表示a到(a+2b-1)的最值
查询区间L到R的最值：找到最大的K，满足(L+2K-1)<=R，那么最值就是f(L,K)与f(R-(1< K=log2(R-L+1)
P3865 ST表模板 题意： 长度为n的数组，m次询问，每次询问[l,r]内的最大值
code:

//这题是求最大值，如果求最小值改一下就行了 #include #include #include #include #include using namespace std; const int maxm=1e5+5; int f[maxm][30]; int maxd; int ask(int l,int r){ int k=(int)(log(r-l+1)/log(2)); return max(f[l][k],f[r-(1<

POJ 3368 Frequent values 题意： 给长度为n的数组a，保证数组非递减
m组询问，每组询问给L,R，问[L,R]中出现次数最多的数出现了多少次
n<=1e5，a(i)<=1e5
思路： 因为数组是非递减的，因此相同的数一定是连续的，
是b(i)表示以位置i为结尾的连续数个数，例如：
a数组：-1 -1 1 1 1 1 3 10 10 10
b数组： 1 2 1 2 3 4 1 1 2 3
这样之后计算区间最大值就是计算b数组的最大值
假如询问[1,10]，最大值是4，那么答案就是4
如果询问[5,10]，发现这段区间b数组为3 4 1 1 2 3，但是答案不是4，因为区间前面有一段被截掉了。
如何解决这个问题呢？
因为只有区间最前面一段和区间最后面一段有可能被截断，
且因为数组非降序，因此截断之后剩下的部分数字一定相同
那么我们可以直接统计最前面一端和最后面一段的，对中间的一段取最值，这样答案就不会错了。
统计前后两端的长度用二分的方法来找相同数的最大位置(或者最小位置)
中间一段的最值，因为不需要修改，可以用st表来实现
code：
#include #include #include #include #include using namespace std; const int maxm=1e5+5; int a[maxm]; int b[maxm]; int n,m; struct ST{ int f[maxm][30]; int maxd; void init(int *x,int l,int r){ maxd=25; //maxd=(int)(log(r-l+1)/log(2))+1; for(int i=l; i<=r; i++){ f[i][0]=x[i]; } for(int j=1; j<=maxd; j++){ for(int i=1; i+(1<r)L=r; if(R

    推荐阅读


    上一篇：vscode编辑器常用快捷键

    下一篇：Python|两种不同方法求最大公约数GCD（Greatest Common Divisor）（Python）