2019第十届蓝桥杯国赛-I第八大奇迹

题面

【问题描述】

在一条 R 河流域，繁衍着一个古老的名族 Z。他们世代沿河而居，也在河边发展出了璀璨的文明。

Z 族在 R 河沿岸修建了很多建筑，最近，他们热衷攀比起来。他们总是在比谁的建筑建得最奇特。

幸好 Z 族人对奇特的理解都差不多，他们很快给每栋建筑都打了分，这样评选谁最奇特就轻而易举了。

于是，根据分值，大家很快评出了最奇特的建筑，称为大奇迹。

后来他们又陆续评选了第二奇特、第二奇特、……、第七奇特的建筑，依次称为第二大奇迹、第三大奇迹、……、第七大奇迹。

最近，他们开始评选第八奇特的建筑，准备命名为第八大奇迹。

在评选中，他们遇到了一些问题。

首先，Z 族一直在发展，有的建筑被拆除又建了新的建筑，新建筑的奇特值和原建筑不一样，这使得评选不那么容易了。

其次，Z 族的每个人所生活的范围可能不一样，他们见过的建筑并不是所有的建筑，他们坚持他们自己所看到的第八奇特的建筑就是第八大奇迹。

Z 族首领最近很头疼这个问题，他害怕因为意见不一致导致 Z 族发生分歧。他找到你，他想先了解一下，民众自己认为的奇迹是怎样的。

现在告诉在 R 河周边的建筑的变化情况，以及在变化过程中一些人的生活范围，请编程求出每个人认为的第八大奇迹的奇特值是多少。

【输入格式】

输入的第一行包含两个整数 $L, N$，分别表示河流的长度和要你处理的信息的数量。开始时河流沿岸没有建筑，或者说所有的奇特值为 $0$。

接下来 $N$ 行，每行一条你要处理的信息。

如果信息为 $C$ $p$ $x$，表示流域中第 $p$ 个位置 ($1 ≤ p ≤ L$) 建立了一个建筑， 其奇特值为 $x$。如果这个位置原来有建筑，原来的建筑会被拆除。

如果信息为 $Q$ $a$ $b$，表示有个人生活的范围是河流的第 $a$ 到 $b$ 个位置（包含 $a$ 和 $b$，$a ≤ b$），这时你要算出这个区间的第八大奇迹的奇特值，并输出。如果找不到第八大奇迹，输出 $0$。

【输出格式】

对于每个为 $Q$ 的信息，你需要输出一个整数，表示区间中第八大奇迹的奇特值。

【样例输入】

10 15 
C 1 10
C 2 20
C 3 30
C 4 40
C 5 50
C 6 60
C 7 70
C 8 80
C 9 90
C 10 100
Q 1 2
Q 1 10
Q 1 8
C 10 1
Q 1 10 

【样例输出】

0
30
10
20 

【评测用例规模与约定】

对于 20% 的评测用例，$1 ≤ L ≤ 1000, 1 ≤ N ≤ 1000$。

对于 40% 的评测用例，$1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000$。

对于 100% 的评测用例，$1 ≤ L ≤ 100000, 1 ≤ N ≤ 100000$。

所有奇特值为不超过 $10^9$ 的非负整数。

思路

线段树，线段树维护区间 $[l, r]$ 内的前八大的数，套板子即可。

代码

#include<iostream>
#include<vector>
#include<cstdio>

using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n, m;

struct SegmentTree {
    int l, r;
    vector<int> dat;
} t[N * 4];

//建树，初始化
void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    t[p].dat.resize(8);
    if (l == r) return;

    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
}

//从大到小 归并两个序列
inline void merge(vector<int> &a, vector<int> &b, vector<int> &c) {
    c.resize(8);
    int i = 0, j = 0, k = 0;
    while (i < 8 && j < 8 && k < 8) {
        if (a[i] >= b[j]) c[k++] = a[i++];
        else c[k++] = b[j++];
    }
    while (i < 8 && k < 8) c[k++] = a[i++];
    while (j < 8 && k < 8) c[k++] = b[j++];
}

//修改位置在 x 的其特质为 v
void change(int p, int x, int v) {
    if (t[p].l == t[p].r) {
        t[p].dat[0] = v;    //该区间只有 单个点，直接修改
        return;
    }

    int mid = (t[p].l + t[p].r) / 2;
    if (x <= mid) change(p * 2, x, v);
    else change(p * 2 + 1, x, v);
    merge(t[p * 2].dat, t[p * 2 + 1].dat, t[p].dat);
}

//查询区间 l, r 内前八大的数
vector<int> query(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p].dat;
    int mid = (t[p].l + t[p].r) / 2;

    if (r <= mid) return query(p * 2, l, r);
    if (mid < l) return query(p * 2 + 1, l, r);
    vector<int> a = query(p * 2, l, r);
    vector<int> b = query(p * 2 + 1, l, r);
    vector<int> res;
    merge(a, b, res);
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    char op;
    int a, b;
    build(1, 1, n);
    while (m--) {
        scanf("\n%c %d %d", &op, &a, &b);
        if (op == 'C') {    //修改
            change(1, a, b);
        } else {  //查询
            printf("%d\n", query(1, a, b)[7]);
        }
    }
    return 0;
}