企业官网建设流程全解析

北京免费公司注册地址,站长工具seo综合查询收费吗,做网站的开场白,中国高清vpswindows在线【模板】静态区间最值_牛客题霸_牛客网 st表基于倍增的思想实现 最大值最小值思路一样 这里以最大值讲解 一个序列的子区间的个数显然有n*n个 根据倍增思想 我们首先在这个规模为n*n的状态空间中选择一些2的整数次幂的位置作为代表值 设f[i][j]表示数列中子区间[i][i2^j-…【模板】静态区间最值_牛客题霸_牛客网st表基于倍增的思想实现最大值最小值思路一样 这里以最大值讲解一个序列的子区间的个数显然有n*n个 根据倍增思想 我们首先在这个规模为n*n的状态空间中选择一些2的整数次幂的位置作为代表值设f[i][j]表示数列中子区间[i][i2^j-1]中的最大值 也就是包括i本身 一段长度为2^j的区间最大值 递推边界显然是f[i][0]a[i] 也就是[i,i]区间中的最大值是本身在递推的时候 我们把子区间成倍增长 有公式f[i][j]max( f[i][j-1], f[i(1(j-1))][j-1] ) 也就是把一个区间的最值 分为了两个区间的最值中更大的那个代码实现int a[N],fmaxn[N][20],fminn[N][20]; void st(){ for(int i1;in;i)fmaxn[i][0]a[i],fminn[i][0]a[i]; int tlog(n)/log(2)1; for(int j1;jt;j){ for(int i1;in-(1j)1;i){ fmaxn[i][j]max(fmaxn[i][j-1],fmaxn[i(1(j-1))][j-1]); fminn[i][j]min(fminn[i][j-1],fminn[i(1(j-1))][j-1]); } } }最值查询部分查询区间[l,r]的最值的时候 我们先计算一个k满足2^kr-l12^(k1) 也就是2的k次幂小于区间长度下 然后比较以l开头的2^k个数的区间中的最大值 和 r结尾的2^k个数字的区间的最大值 因为求的是最值 所以这两个区间可以重叠 但是必须包含所有的元素查询代码实现int query(int op,int l,int r){ int klog(r-l1)/log(2); if(op1)return min(fminn[l][k],fminn[r-(1k)1][k]); if(op2)return max(fmaxn[l][k],fmaxn[r-(1k)1][k]); }该题完整代码实现#include bits/stdc.h using namespace std; int n,q; const int N5e55; int a[N],fmaxn[N][20],fminn[N][20]; void st(){ for(int i1;in;i)fmaxn[i][0]a[i],fminn[i][0]a[i]; int tlog(n)/log(2)1; for(int j1;jt;j){ for(int i1;in-(1j)1;i){ fmaxn[i][j]max(fmaxn[i][j-1],fmaxn[i(1(j-1))][j-1]); fminn[i][j]min(fminn[i][j-1],fminn[i(1(j-1))][j-1]); } } } int query(int op,int l,int r){ int klog(r-l1)/log(2); if(op1)return min(fminn[l][k],fminn[r-(1k)1][k]); if(op2)return max(fmaxn[l][k],fmaxn[r-(1k)1][k]); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinnq; for(int i1;in;i)cina[i]; st(); while(q--){ int op,l,r; cinoplr; coutquery(op,l,r)\n; } return 0; }