咸阳网站建设有哪些,广州产品设计公司有哪些,西安市建设工程信息网新平台,网站百度收录要多久[传送门](https://www.luogu.com.cn/problem/P38
解析
板子题最棒了 用mx[i][j]存储以i为起点#xff0c;长度为2^j次方的区间内的max 分成前后两段#xff0c;则可以得到递推式#xff1a;
mx[i][k]max(mx[i][k-1],mx[imi[k-1]][k-1]);而关于初始化#xff0c;显然长度为2^j次方的区间内的max 分成前后两段则可以得到递推式
mx[i][k]max(mx[i][k-1],mx[imi[k-1]][k-1]);而关于初始化显然
mx[i][0]a[i];预处理时间复杂度为nlogn 对于任意长度[l,r] 我们可以找到不大于其长度的最大的2^k 则max[l,r]max(mx[l][k],mx[r - (1 k) 1][k]) 画图大概就是这样子滴 (《神笔马良》 用两段的最大值合并即整体的最大值 从而在O1的时间内完成单次询问的查询 问题解决
代码
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includeiostream
#includestring
#includequeue
#includevector
using namespace std;
int n,m;
int a[100500];
int mx[100500][17];//mx[i][j]以i起点长度为2^j次方中的max
int mi[20];
int q[100500];
void solve(){mi[0]1;for(int i1;i18;i){mi[i]mi[i-1] * 2;}int k1;for(int i1;in;i){if(mi[k]i) k;q[i]k-1;}
}
int main(){scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,a[i]);mx[i][0]a[i];}solve();for(int k1;mi[k]n;k){for(int i1;i(1k)-1n;i){mx[i][k]max(mx[i][k-1],mx[imi[k-1]][k-1]);//printf(%d ,mx[i][k]);}//printf(\n);}for(int k1;km;k){int st,ed;scanf(%d%d,st,ed);int jq[ed-st1];int ansmax(mx[st][j],mx[ed-mi[j]1][j]);printf(%d\n,ans);}return 0;
}AC快乐
