二、程序阅读题（每个小题单独作答，共40分）

程序阅读（3）：区间次大值

输入满足 n,q<=100000、-10^9<=a[i]<=10^9、1<=L<=R<=n。这里的“次大值”允许与最大值相等。

#include <bits/stdc++.h>
using namespace std;
int n, q, a[100005], dp[100005][20][2];
void init(){
    for (int i = 1; (1 << i) <= n; i++){
        for (int L = 1; L + (1 << i) - 1 <= n; L++){
            dp[L][i][0] = max(dp[L][i - 1][0], dp[L + (1 << (i - 1))][i - 1][0]);
            dp[L][i][1] = min(
                max(dp[L][i - 1][1], dp[L + (1 << (i - 1))][i - 1][0]),
                max(dp[L][i - 1][0], dp[L + (1 << (i - 1))][i - 1][1])
            );
        }
    }
}
int query(int L, int R){
    int a = -2e9, b = -2e9, M = 0;
    while (L + (1 << (M + 1)) - 1 <= R) M++;
    for (int i = M; i >= 0; i--){
        if (L + (1 << i) - 1 > R) continue;
        if (dp[L][i][0] > a){
            b = max(a, dp[L][i][1]);
            a = dp[L][i][0];
        }
        else b = max(b, dp[L][i][0]);
        L += (1 << i);
    }
    return b;
}
int main(){
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        dp[i][0][0] = a[i];
        dp[i][0][1] = -2e9;
    }
    init();
    while (q--){
        int L, R; scanf("%d%d", &L, &R);
        printf("%d\n", query(L, R));
    }
    return 0;
}

输入如下时，输出是（ ）。

4 2
1 3 2 4
1 3
2 4

{{ select(1) }}

• 1 2
• 2 3
• 3 3
• 3 4