```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+10;//注意范围
const ll M=(ll)(log2(N));
ll n,m;
ll a[N][M];
ll luogu(ll x,ll y) {
ll k=(ll)(log2(y-x+1));
return max(a[x][k],a[y-(1<<k)+1][k]);
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1; i<=n; i++) scanf("%lld",&a[i][0]);
for(ll j=1; (1<<j)<=n; j++)
for(ll i=1; i+(1<<j)-1<=n; i++)
a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]);
while(m--) {
ll x,y;
scanf("%lld%lld",&x,&y);
ll t=luogu(x,y);
printf("%lld\n",t);
}
return 0;
}//给个关吧谢谢
```
@[Hinluogu](/user/1180231)
by z_z_b_ @ 2024-04-12 18:55:45
luogu(x,y) 里面的k不建议用log2算
应该是精度问题
建议先把1~n所有数的log2先用递推预处理
要用直接访问数组,应该就不会被卡了
by lbmzxhb @ 2024-04-12 18:57:58
```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+10;
const ll M=(ll)(log(N)/log(2));
ll n,m;
ll a[N][M];
ll luogu(ll x,ll y) {
ll k=(ll)(log(y-x+1)/log(2));
return max(a[x][k],a[y-(1<<k)+1][k]);
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1; i<=n; i++)
scanf("%lld",&a[i][0]);
for(ll j=1; (1<<j)<=n; j++)
for(ll i=1; i+(1<<j)-1<=n; i++)
a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]);
while(m--) {
ll x,y;
scanf("%lld%lld",&x,&y);
ll t=luogu(x,y);
printf("%lld\n",t);
}
return 0;
}
```
by H_dream @ 2024-04-12 19:00:05
(ll)log2(N)=16
2^16=65536
2^17=131072
所以......
```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+10;
const ll M=(ll)(log(N)/log(2))+1;//更改处
ll n,m;
ll a[N][M];
ll luogu(ll x,ll y) {
ll k=(ll)(log(y-x+1)/log(2));
return max(a[x][k],a[y-(1<<k)+1][k]);
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1; i<=n; i++)
scanf("%lld",&a[i][0]);
for(ll j=1; (1<<j)<=n; j++)
for(ll i=1; i+(1<<j)-1<=n; i++)
a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]);
while(m--) {
ll x,y;
scanf("%lld%lld",&x,&y);
ll t=luogu(x,y);
printf("%lld\n",t);
}
return 0;
}
```
by H_dream @ 2024-04-12 19:03:26
@[z_z_b_](/user/956129)
@[lbmzxhb](/user/688191)
感谢二位大佬
此贴已结
by H_dream @ 2024-04-12 19:06:32