社区讨论

为什么ios::sync_with_stdio(false); 这个万能方法都过不了……

P3865【模板】ST 表 & RMQ 问题参与者 9已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@mi6ldoru
此快照首次捕获于
2025/11/20 06:46
4 个月前
此快照最后确认于
2025/11/20 07:00
4 个月前
查看原帖
···
CPP
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int N, M, a[100010], f[100010][20];
//定义f[i][j]为i到i+2^j-1区间的最大值
void prepar()
{
    for (int i = 1; i <= N; i++) f[i][0] = a[i];
    for (int j = 1; (1 << j) <= 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]);
}//二分来预处理,时间复杂度O(nlogn)
CPP
int getans(int l, int r)
{
    int k = int(log(r - l + 1) / log(2));
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        cin >> a[i];
    prepar();
    while (M--)
    {
        int l, r;
        cin >> l >> r;
        cout << getans(l, r) << endl;
    }
    return 0;
}
···

回复

12 条回复,欢迎继续交流。

正在加载回复...