题解

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;
const int MAXN = 2e5 + 5;

int N, Q;
int tree[4 * MAXN]; // 线段树，存储每个年龄的最新下车车站

// 更新线段树
void update(int idx, int l, int r, int pos, int val) {
if (l == r) {
tree[idx] = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) {
update(2 * idx, l, mid, pos, val);
} else {
update(2 * idx + 1, mid + 1, r, pos, val);
}
tree[idx] = min(tree[2 * idx], tree[2 * idx + 1]);
}

// 查询区间 [ql, qr] 中第一个满足车站值 ≤ Y 的年龄
int query(int idx, int l, int r, int ql, int qr, int Y) {
if (r < ql || l > qr) return -1; // 超出查询范围
if (tree[idx] > Y) return -1; // 整个区间的最小车站都大于Y

if (l == r) {
    return l; // 找到满足条件的最小年龄
}

int mid = (l + r) / 2;
// 先查左子树（年龄较小的部分）
int left_res = -1;
if (ql <= mid) {
    left_res = query(2 * idx, l, mid, ql, min(qr, mid), Y);
    if (left_res != -1) return left_res;
}
// 左子树没找到再查右子树
if (qr > mid) {
    return query(2 * idx + 1, mid + 1, r, max(ql, mid + 1), qr, Y);
}
return -1;

}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> N >> Q;

// 初始化线段树，所有值设为无穷大
for (int i = 0; i < 4 * MAXN; i++) {
    tree[i] = INF;
}

while (Q--) {
    char op;
    cin >> op;
    if (op == 'M') {
        int X, A;
        cin >> X >> A;
        update(1, 1, N, A, X);
    } else {
        int Y, B;
        cin >> Y >> B;
        int ans = query(1, 1, N, B, N, Y);
        cout << ans << '\n';
    }
}

return 0;

}