```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=50050, M=30;//开小了
int n,q;
int a[N][M],b[N][M];
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i][0]);
b[i][0]=a[i][0];
}
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){//注意大小
a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]);
b[i][j]=min(b[i][j-1],b[i+(1<<(j-1))][j-1]);//哥,ab数组不分啊!!!
}
}
while(q--){
int x,y;scanf("%d%d",&x,&y);
int k=log2(y-x+1);//能直接用log2的
int xx=max(a[x][k],a[y-(1<<k)+1][k]);
int yy=min(b[x][k],b[y-(1<<k)+1][k]);
printf("%d\n",xx-yy);
}
return 0;
}
```
@[Hinluogu](/user/1180231)
by z_z_b_ @ 2024-04-13 15:46:21
直接ctrl下来了
[感谢]
@[z_z_b_](/user/956129)
此贴已结
by H_dream @ 2024-04-13 16:01:17