改了一下 还是80分
```c
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int f[100005][20];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main(){
int n,m;
n=read();
m=read();
for(int i=1; i<=n; i++){
f[i][0]=read();
}
for(int j=1; j<=log2(n); j++){
for(int i=1; i+(1<<j-1)<=n; i++){
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
for(int i=1; i<=m; i++){
int x,y;
x=read();
y=read();
int k=log2(y-x+1);
cout<<max(f[x][k],f[y-(1<<k)+1][k])<<endl;
}
return 0;
}
```
by wsqin_qwq @ 2023-01-12 16:16:35
@[wusiqin](/user/849486) 建议你开头先预处理 `lg[i]=log2(i)`。
这样可以做到询问 $\mathcal{O }(1)$
by lzyqwq @ 2023-01-12 16:18:53
@[蒟蒻·廖子阳](/user/539211) orz
by wsqin_qwq @ 2023-01-12 16:23:07
@[蒟蒻·廖子阳](/user/539211) 还是TLE
by wsqin_qwq @ 2023-01-12 16:36:44
```c
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int f[100005][20];
int lg[2000005];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main(){
int n,m;
n=read();
m=read();
for(int i=1; i<=n; i++){
f[i][0]=read();
}
lg[1]=0;
for(int i=2; i<=n; i++){
lg[i]=lg[i/2]+1;
}
for(int j=1; j<=lg[n]; j++){
for(int i=1; i+(1<<j-1)<=n; i++){
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
for(int i=1; i<=m; i++){
int x,y;
x=read();
y=read();
int k=lg[y-x+1];
cout<<max(f[x][k],f[y-(1<<k)+1][k])<<endl;
}
return 0;
}
```
by wsqin_qwq @ 2023-01-12 16:37:11
@[wusiqin](/user/849486) 换printf
```cpp
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int f[100005][20];
int lg[2000005];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main(){
int n,m;
n=read();
m=read();
for(int i=1; i<=n; i++){
f[i][0]=read();
}
lg[1]=0;
for(int i=2; i<=n; i++){
lg[i]=lg[i/2]+1;
}
for(int j=1; j<=lg[n]; j++){
for(int i=1; i+(1<<j-1)<=n; i++){
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
for(int i=1; i<=m; i++){
int x,y;
x=read();
y=read();
int k=lg[y-x+1];
printf("%d\n",max(f[x][k],f[y-(1<<k)+1][k]));
}
return 0;
}
```
by w9095 @ 2023-01-12 16:41:35
https://www.luogu.com.cn/record/99496102
by w9095 @ 2023-01-12 16:41:57
@[w9095](/user/569235) %%%%%%%(cout复杂度那么高的马
by wsqin_qwq @ 2023-01-12 16:43:34
小优化:
for(int i=1; i+(1<<j-1)<=n; i++)
这边多运行了
改为for(int i=1;i+(1<<j)-1<=n;++i)
by 137QWQ @ 2023-01-12 16:44:22
@[wusiqin](/user/849486) cout本来就慢,你还endl清空缓存区,这么大的输出量不T才怪
by w9095 @ 2023-01-12 16:44:28