码风有点丑,大家将就帮帮我这个蒟蒻
by I_love_LPN_Forever @ 2022-03-08 11:01:24
@[Lovely_z](/user/525056)
lg数组没用吧(STL很慢,但应该不是问题所在
by ningago @ 2022-03-08 11:07:15
@[Lovely_z](/user/525056)
还有题目中的快速读入
by ningago @ 2022-03-08 11:07:55
@[Lovely_z](/user/525056) `lg[i] = lg[i / 2] + 1;`
数组越界了
by recollector @ 2022-03-08 11:10:12
``lg``从2开始,枚举到``maxn``吧
by ningago @ 2022-03-08 11:11:08
谢谢大佬们,ac了
by I_love_LPN_Forever @ 2022-03-08 11:11:33
顺便说一句,不用预处理 lg 数组,用 `31 - __builtin_clz(n)` 会更快
by zghtyarecrenj @ 2022-03-08 11:12:20
lg数组删了就行了,应该是越界的问题
主要我刚学数据结构,不是很熟练
by I_love_LPN_Forever @ 2022-03-08 11:12:28
@[Lovely_z](/user/525056)
* `for` 循环中要用快读
* `lg` 数组开小了, 要开 `maxn`
* `lg[0] = 1` 要加在开头
* ~~你预处理了 lg 为什么要用 log2~~
by JDS070115 @ 2022-03-08 11:13:30
改后代码:
```cpp
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
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 f[maxn][31];
int n, m;
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) {
f[i][0] = read();
}
for (int j = 1; j <= 30; 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, x, y, k; i <= m; i++) {
x = read(), y = read();
k = log2(y - x + 1);
//cout << max(f[x][k], f[y - (1 << k) + 1][k]) << endl;
printf("%d\n", max(f[x][k], f[y - (1 << k) + 1][k]));
}
return 0;
}
```
by I_love_LPN_Forever @ 2022-03-08 11:14:27