zhejiushishi
2024-09-16 17:28:26
发布于:广东
论某知识点
设表示从出发,往后走步的最大值
然后
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=5e4+10,M=16;
int n,q,a[N],f[N][M],g[N][M],lg[N];
void init(){
for(int i=1;i<=n;i++) while(1<<(lg[i]+1)<=i)lg[i]++;
for(int j=0;1<<j<=n;i++){
for(int i=1;i+(1<<j)-1<=n;i++){
if(!j) f[i][j]=g[i][j]=a[i];
else{
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
}
}
}
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
init();
while(q--){
int l,r;
cin>>l>>r;
int t=lg[r-l+1];
int maxh=max(f[l][r],f[r-(1<<t)+1][t]);
int minh=min(g[l][t],g[r-(1<<t)+1][t]);
cout<<maxh-minh<<endl;
}
return 0;
}
平方和公式:
立方和公式
这里空空如也
有帮助,赞一个