改成cout << rmq(l, r) << '\n' 试试
by peaneevall_kalaa @ 2022-08-13 08:44:23
@[Bker_](/user/221551)
```
cout<<rmq(l , r)<<endl;
```
cout /n 奇慢无比
属于是buff叠满了
by dlydly @ 2022-08-13 08:44:23
@[Bker_](/user/221551)
```
#include <bits/stdc++.h>
using namespace std;
int a[2000010][25] = {0};
int n , m ;
inline int read(){
int x = 0 ; int f = 1 ; char c = getchar() ;
while(c < '0' || c > '9') {if(c == '-') f = -1 ; c = getchar() ;}
while(c >= '0' && c <= '9') {x = x * 10 + c - 48 ; c = getchar() ;}
return x * f ;
}
inline unsigned int LOG2(unsigned int x)
{
unsigned int ret;
__asm__ __volatile__(
"bsrl %1, %%eax"
: "=a"(ret)
: "m"(x));
return ret;
}
void pre(){
for(register int i = 1 ; i <= n ; i++)
a[i][0] = read() ;
}
void st(){
for (register int j = 1; j < 21; ++j)
for(register int i = 1 ; i + (1 << j) - 1 <= n ; i++)
a[i][j] = max(a[i][j - 1] , a[i + (1 << (j - 1))][j - 1]) ;
}
inline int rmq(int l , int r){
int k = LOG2(r - l + 1) ;
return max(a[l][k] , a[r - (1 << k) + 1][k]) ;
}
int main(){
n = read() , m = read() ;
pre() ;
st() ;
while(m--){
int l , r ;
l =read() , r = read();
printf("%d\n",rmq(l,r));
// cout<<rmq(l , r)<<endl;
}
return 0 ;
}
```
修改了些许,过了
by dlydly @ 2022-08-13 08:45:06
@[Bker_](/user/221551)
1. 试试最后用printf()?
2. log2预处理?
by 大眼仔Happy @ 2022-08-13 08:45:13
@[Bker_](/user/221551) log2函数最好预处理一下,就像这样:
```cpp
for(int i=2;i<=n;++i)
lg2[i]=lg2[i>>1]+1;
```
by WanderingTrader @ 2022-08-13 08:46:40
@[Bker_](/user/221551) 些许指
```
for (register int j = 1; j < 21; ++j)
```
```
printf("%d\n",rmq(l,r));
```
```
int k = LOG2(r - l + 1) ;
```
by dlydly @ 2022-08-13 08:47:05
@[大眼仔Happy](/user/537046)
输出换成了prinf过了
stl里的log函数不是说时间复杂度近似的可以看做O(1)吗 /疑惑
by Bker_ @ 2022-08-13 09:09:02
@[dlydly](/user/124786)
您的LOG2函数是什么原理呢?
/疑惑
by Bker_ @ 2022-08-13 09:09:44
@[Bker_](/user/221551) 底层汇编,奇淫技巧,速度达到极致,薄纱log2(((
bsf 从最高位向最低位进行扫描直到找到第一个 1 为止
其实自己也不太懂啦
by dlydly @ 2022-08-13 09:19:25
@[Bker_](/user/221551) 不需要多余的空间占用,堪称完美。
by dlydly @ 2022-08-13 09:20:08