#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n[200005], m,a,b,c,d; int correct(int c1, int c2) { int j = 0; for (int i = c1; i <= c2; i++) j = max(n[i], j); return j; } 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 i = 1; cin >> a >> b; for(i;i<=a;i++) n[i] = read(); while (b--) { cin >> c >> d; cout << correct(c, d) << endl;; } return 0; }怎么改成时间复杂度O(1)

要将上述代码的时间复杂度优化为O(1)，可以通过预处理数组来实现。以下是修改后的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n[200005], m, a, b, c, d;
int maxVal[200005];

int correct(int c1, int c2)
{
    return maxVal[c2] - maxVal[c1 - 1];
}

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 i = 1;
    cin >> a >> b;

    for (i; i <= a; i++)
        n[i] = read();

    // 预处理数组，计算从1到i的最大值
    for (int i = 1; i <= a; i++)
        maxVal[i] = max(maxVal[i - 1], n[i]);

    while (b--)
    {
        cin >> c >> d;
        cout << correct(c, d) << endl;;
    }
    return 0;
}

在这个修改后的代码中，我们使用了一个新的数组`maxVal`来存储从1到i的最大值。在预处理阶段，我们计算出每个位置的最大值，并将其存储在`maxVal`数组中。这样，当需要计算c到d范围内的最大值时，我们只需要通过`maxVal[d] - maxVal[c - 1]`来获取结果，而不需要遍历整个范围。这样，时间复杂度就优化为O(1)了。