A40226. 第八大奇迹
题目描述
第八大奇迹
题目描述
在一条 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 的信息，你需要输出一个整数，表示区间中第八大奇迹的奇特值。
数据范围
1≤L≤100000，
1≤N≤100000，
所有奇特值为不超过 109 的非负整数。
输入样例：
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
参考答案
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
template <typename T> inline void read(T &x) {
x = 0; T f = 1;char s = getchar();
for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
for(; isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
x *= f;
}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define _srep(n,m,i)for (register int i = (n); i >= (m); i--)
#define _sfor(n,m,i)for (register int i = (n); i > (m); i--)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
int a[N];
struct node {
int op, x, y, k, id;
}e[N*10], lq[N], rq[N];
int cnt, ans[N];
int T[N];
int n, L;
void upd(int pos, int val) {
for(; pos <= L; pos += lowbit(pos)) T[pos] += val;
}
int qry(int pos) {
int res = 0;
for(; pos; pos -= lowbit(pos)) res += T[pos];
return res;
}
void solve(int vl, int vr, int ql, int qr) {
if(ql > qr || vl > vr) return ;
if(vl == vr) {
for(int i = ql; i <= qr; ++i) {
if(e[i].op == 2) ans[e[i].id] = vl;
}
return ;
}
int mid = vl + vr >> 1, l = 0, r = 0;
for(int i = ql; i <= qr; ++i) {
if(e[i].op == 1) {
if(e[i].y > mid) {
upd(e[i].x, e[i].k);
rq[++r] = e[i];
} else {
lq[++l] = e[i];
}
} else {
int k = qry(e[i].y) - qry(e[i].x-1);
if(k < e[i].k) {
e[i].k -= k;
lq[++l] = e[i];
} else {
rq[++r] = e[i];
}
}
}
for(int i = ql; i <= qr; ++i) {
if(e[i].op == 1 && e[i].y > mid) {
upd(e[i].x, -e[i].k);
}
}
for(int i = 1; i <= l; ++i) e[i+ql-1] = lq[i];
for(int i = 1; i <= r; ++i) e[i+ql+l-1] = rq[i];
solve(vl, mid, ql, ql+l-1);
solve(mid+1, vr, ql+l, qr);
}
int main() {
read(L); read(n);
char op[3];
memset(ans, -1, sizeof ans);
for(int i = 1, x, y; i <= n; i++) {
scanf("%s %d %d", op, &x, &y);
if(op[0] == 'C') {
if(a[x]) {
e[++cnt] = node {1, x, a[x], -1};
e[++cnt] = node {1, x, y, 1};
a[x] = y;
} else {
e[++cnt] = node {1, x, y, 1};
a[x] = y;
}
} else {
e[++cnt] = node {2, x, y, 8, i};
}
}
solve(0, 1e9, 1, cnt);
for(int i = 1; i <= n; ++i) {
if(~ans[i]) {
printf("%d\n", ans[i]);
}
}
}