【题解】LuoGu4422：Deda

原题传送门 这是二维偏序，注意到每个小朋友的年龄为$1-n$不同 可以按照小朋友的年龄为线段树的下标，维护一段小朋友区间中最小的站台 每次$update$暴力把所有包含这个小朋友的区间更新，这个部分稳定$O(nlogn)$ 每次$query$先看看能不能往左找到满足的小朋友，不行看看往右走可不可以 算是一个常数比较大的线段树

Code：

#include <bits/stdc++.h> #define maxn 200010 #define ls rt << 1 #define rs rt << 1 | 1 using namespace std; const int inf = 2000000000; struct Seg{ int l, r, sum; }seg[maxn << 3]; int n, m; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } void pushup(int rt){ seg[rt].sum = min(seg[ls].sum, seg[rs].sum); } void build(int rt, int l, int r){ seg[rt].l = l, seg[rt].r = r, seg[rt].sum = inf; // printf("BUild:%d %d %d\n", seg[rt].l, seg[rt].r, seg[rt].sum); if (l == r) return; int mid = (l + r) >> 1; build(ls, l, mid), build(rs, mid + 1, r); } void update(int rt, int y, int x){ if (seg[rt].r < y || seg[rt].l > y) return; seg[rt].sum = min(seg[rt].sum, x); // printf("Update:%d %d %d\n", seg[rt].l, seg[rt].r, seg[rt].sum); update(ls, y, x), update(rs, y, x); } int query(int rt, int y, int x){ if (seg[rt].r < y) return inf; // printf("Query:%d %d %d\n", seg[rt].l, seg[rt].r, seg[rt].sum); if (seg[rt].l == seg[rt].r) return seg[rt].l; int ans = inf; if (seg[ls].sum <= x) ans = min(ans, query(ls, y, x)); if (ans < inf) return ans; // printf("%d\n", x); if (seg[rs].sum <= x) ans = min(ans, query(rs, y, x)); return ans; } int main(){ freopen("deda.in", "r", stdin); freopen("deda.out", "w", stdout); n = read(), m = read(); build(1, 1, n); while (m--){//printf("%d\n", seg[3].sum); char opt = getchar(); for (; opt != 'D' && opt != 'M'; opt = getchar()); int x = read(), y = read(); if (opt == 'D'){ int ans = inf; if (seg[1].sum <= x) ans = min(ans, query(1, y, x)); if (ans == inf) puts("-1"); else printf("%d\n", ans); } else update(1, y, x); } return 0; }