天使果冻

题目链接：nowcoder 219641

到主站看：https://blog.csdn.net/weixin_43346722/article/details/115710679

题目大意

要你求前 1~n 个数字中，第二大的数字。
如果有多个最大，第二大就是最大。

思路

这是个多次询问去区间第二大。

由于左端点固定是 1，我们可以直接从左往右枚举右端点，然后每次新放进去一个数。
然后就维护前两大的值，最后判断一下最大的值出现的次数，看是输出最大的还是第二大的就可以了。

代码

#include<cstdio>

using namespace std;

int n, a[100001], x;
int ans[100001], maxn, maxx, maxn2, maxx2;

int read() {
    char c = getchar();
    int re = 0;
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        re = (re << 3) + (re << 1) + c - '0';
        c = getchar();
    }
    return re;
}

void write(int now) {
    if (now > 9) write(now / 10);
    putchar(now % 10 + '0');
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        if (a[i] > maxn) {//维护前两大的值
            maxn2 = maxn;
            maxx2 = maxx;
            maxn = a[i];
            maxx = 1;
        }
        else if (a[i] == maxn) {
            maxx++;
        }
        else if (a[i] > maxn2) {
            maxn2 = a[i];
            maxx2 = 1;
        }
        else if (a[i] == maxn2) {
            maxx2++;
        }
        if (maxx > 1) ans[i] = maxn;//如果最大的出现多次就选最大的，否则选第二大的
            else ans[i] = maxn2;
    }

    n = read();
    while (n--) {
        x = read();
        write(ans[x]);
        putchar('\n');
    }

    return 0;
}