外层线段树按 x 组存区间最大 y，靠「整段最大值不够就剪掉」单路下降定位最左可行 x；组内可用 std::set 或离线压缩后的 Fenwick 维护。
OJ: codeforces
题目 ID: 19D
难度:提高+/省选-
标签:线段树二分树状数组坐标压缩二维查询集合pythoncpp
创建: 2026-07-16 23:59
更新: 2026-10-28 17:33
形式化题目
平面上动态维护一个点集
add x y：插入点，保证该点当前不在 中； remove x y：删除点，保证该点当前在 中； find x y：在满足且 的点中，先取 最小者，若仍不唯一再取 最小者，输出该点；无解输出 。
也就是每次询问一个「严格右上」的半平面里字典序最小的点。所有坐标不超过
结构上的关键是：
解法总览
两个解法的外层完全一样，差别只在「一个
- 解法一（
main.cpp，正式主解）：外层线段树按分组建，结点存这段 里所有点的最大 ；组内用 std::set<int>存活跃。查询时先靠线段树单路下降找到最左可行组，再在该组的 set上upper_bound。全程在线，不需要先读完输入。 - 解法二（
main2.cpp/main2.py）：外层同一棵线段树；组内换成「离线坐标压缩 + Fenwick 计数树」，用「前缀计数 +kth二进制提升」定位第一个大于query_y的活跃。结构全是数组，常数更小，也是 Python 侧唯一现实可行的写法。
两个解法的复杂度同为
| 解法 | 核心观察 | 复杂度 | 适用场景 | 对应代码 |
|---|---|---|---|---|
解法一：组内 std::set |
结点存组区间最大 set 天然有序 |
每次 |
强制在线、或不想写离线压缩 | main.cpp（C++） |
| 解法二：组内 Fenwick | 同一棵树，组内改为「活跃 kth 定位 |
每次 |
允许离线、追求常数；Python 侧唯一可行 | main2.cpp（C++）、main2.py（Python） |
同目录的 brute.cpp 是「每次 find 扫一遍所有点」的暴力，只作为对拍基线，不单独成章——它每次询问
解法一：组内 std::set + 外层线段树带剪枝下降
思路
先想法把二维压成一维。 所有 add 出现过的
- 在组序列里，从「第一个
的组」开始往右，找第一个组内存在某个 的组； - 在那个组里找最小的
。
第 2 步就是有序集合的 upper_bound，std::set<int> 直接给。真正要想清楚的是第 1 步。
下面三张图用一份专门构造的教学数据（不是题目样例）走完整条流程：7 个组、组 2 和组 5 已被删空、查询 find 3 3，最终答案是
竖着看每一列就是一个组，组内就是 std::set 里的元素；柱顶那根绿线是该组的最大
第 1 步不能对着「组内最大
组下标 j : 1 2 3 4
组内最大 y m_j : 5 1 1 6
m_j > 4 : 真 假 假 真 <- 不是一段假接一段真
max(m_1..m_j)>4 : 真 真 真 真 <- 换成前缀最大值才单调若按「第一个
再往前一步：判据本来就存在结点上，不必真做二分。 线段树每个结点维护它覆盖的那段组上的最大
- 该结点的区间整段落在起点左边（
）：与答案无关，剪掉； - 该结点最大值
：这段里每个组都没有 的点，整段剪掉； - 否则答案可能在段内：先走左儿子，左儿子没有再走右儿子；
- 走到叶子（
）时返回该组号——它必然满足组内最大 。
先左后右保证拿到的是最小的组号，也就是最小的
第二张图把同一次 find 3 3 的下降过程画在树上，绿框右上角的编号就是下降顺序：
从根 mid=(l+r)>>1 切分的自然结果，不影响正确性。
两个剪枝条件都要有。只判
组的最大 add/remove 只改一个组：在组内 set 上插入或删除一个 set 的最大元素（rbegin()）写到线段树对应的叶子上，向上更新祖先。空组写
第三张图把「落地到组内」和「改回去」这两件事并排放，左栏是 find 的最后一步，右栏是 remove 的维护：
左栏：组 6 的 set 里是 upper_bound 直接返回第一个跳出来的 set 的 rbegin()），不是单独存一份，所以删掉组 6 的 add/remove 的代价。
这份代码全程用闭区间 [l,mid] 和 [mid+1,r]，叶子是 l==r，越界剪枝写 r < start。组号从 find_first 找不到时返回 find 的 add 里出现过，用 upper_bound 求起点时它会落到最后一组之后，此时 start > g_{\text{组数}}，第一个剪枝条件立刻把所有区间剪掉，同样返回
代码
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-02
* update_at: 2026-10-28 15:10
*/
/* CF19D Points —— 解法一：每组一个 std::set + 外层线段树带剪枝单路下降 */
/* 外层按 x 分组建线段树，结点存该区间内所有点的最大 y；
* 剪枝条件 seg[p] <= query_y 表示整段一个答案都没有，直接砍掉，
* 于是「第一个 x 更大且组内存在 y 更大」的组可以在 O(log n) 内单路下降定位；
* 组内 y 交给 std::set 的顺序性，upper_bound 一次就拿到最小可行 y。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n; // 操作数
char op[MAXN]; // 'a' add / 'r' remove / 'f' find
int ox[MAXN], oy[MAXN]; // 操作参数；坐标不超过 1e9，用 int 省内存
vector<int> xs; // 所有 add 出现过的 x（升序去重），组号 = 下标 + 1
set<int> group_y[MAXN]; // group_y[g]：第 g 组当前挂着的所有 y
int seg[MAXN * 4]; // seg[p]：第 p 个结点覆盖的组区间内最大 y，空组为 -1
int groups; // 组数，线段树下标范围是 [1, groups]
// 点更新：把第 pos 组的叶子值改成 value，并向上合并区间最大值。
void seg_update(int p, int l, int r, int pos, int value) {
if (l == r) {
seg[p] = value;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
seg_update(p << 1, l, mid, pos, value);
else
seg_update(p << 1 | 1, mid + 1, r, pos, value);
seg[p] = max(seg[p << 1], seg[p << 1 | 1]);
}
// 在线段树上找最小的组号 g 使 start <= g 且第 g 组的最大 y > y（线段树二分），
// 不存在返回 0。start 之前（含）的区间整体没有意义，用 r < start 一并剪掉。
int find_first(int p, int l, int r, int start, int y) {
if (r < start || seg[p] <= y) return 0; // 整段在起点左边，或整段最大值都够不到 y
if (l == r) return l; // 走到叶子，它一定满足最大 y > y
int mid = (l + r) >> 1;
int res = find_first(p << 1, l, mid, start, y); // 先左后右，返回的组号自然最小
if (res) return res;
return find_first(p << 1 | 1, mid + 1, r, start, y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s >> ox[i] >> oy[i];
op[i] = s[0];
if (op[i] == 'a') xs.push_back(ox[i]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
groups = xs.size();
fill(seg, seg + 4 * groups + 4, -1); // 初始一个点都没有，所有组都按空组算
for (int i = 0; i < n; i++) {
if (op[i] != 'f') { // add / remove：只改动一个组的点集
int g = lower_bound(xs.begin(), xs.end(), ox[i]) - xs.begin() + 1; // 组号从 1 开始
if (op[i] == 'a')
group_y[g].insert(oy[i]);
else
group_y[g].erase(oy[i]);
seg_update(1, 1, groups, g, group_y[g].empty() ? -1 : *group_y[g].rbegin());
continue;
}
// find：先定位最左的可行组，再在组内取第一个严格大于 query_y 的 y
int start = upper_bound(xs.begin(), xs.end(), ox[i]) - xs.begin() + 1; // 严格大于 query_x 的第一个组号
int g = find_first(1, 1, groups, start, oy[i]);
if (g == 0) {
cout << "-1\n";
continue;
}
int answer_y = *group_y[g].upper_bound(oy[i]);
cout << xs[g - 1] << ' ' << answer_y << '\n';
}
return 0;
}复杂度
预处理是对至多 set 结点：add/remove 是 set 一次插入/删除 + 线段树一次更新），find 是 upper_bound）。总时间
解法二：组内 Fenwick 计数树 + 外层线段树
思路
外层那棵树不动，只把「组内容器」从平衡树换成一个计数树。
先离线读完所有操作，顺便把所有会被插入的点收集起来；按
组内要回答的两件事都能化成秩问题：
- 组内最大
：设该组当前活跃点数为 ，则最大 就是该组第 个活跃 。用 Fenwick 的 kth（二进制提升）一次定位。空组直接取。 - 第一个大于
的活跃 ：先用前缀和数出 的活跃点个数 ，那么答案是第 个活跃 ，同样一次 kth。
kth 的二进制提升就是在计数树上找「最小前缀和达到
外层仍然是解法一那套：结点存组区间最大
Python 侧只能走这条路线。 Python 的 set 只能判存在、不能 upper_bound，标准库也没有平衡树，所以解法一的组内容器在 Python 里没有等价物；而「离线压缩 + 数组 Fenwick」只用 array 和 bisect，可以完整复刻，这也是 main2.py 的写法。代价是很明显的：必须先把输入全部读完，无法边读边答。
代码
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-02
* update_at: 2026-10-28 15:18
*/
/* CF19D Points —— 解法二：每组一个 Fenwick + 外层线段树带剪枝单路下降 */
/* 离线坐标压缩：每个 x 组用 Fenwick 维护活跃 y，外层线段树存每组最大 y。
* find 时先在线段树找第一个 x 更大且最大 y 更大的组，
* 再在该组 Fenwick 里找第一个大于 query_y 的活跃 y。
* 与解法一的差别只在组内容器：这里用离线压缩后的 Fenwick 计数树，
* 组内定位靠「前缀计数 + kth 二进制提升」，不需要 std::set 的结点开销。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
int n; // 操作数
char op[MAXN];
long long ox[MAXN], oy[MAXN]; // 操作参数
vector<long long> xs; // 所有出现过的 x（升序去重），下标即组号
vector<long long> ys; // 每个组的 y 连续存放
vector<int> yoff; // yoff[g]..yoff[g+1] 是组 g 的 y 区间
vector<long long> fenwick; // 所有组的 Fenwick 共享一块数组
vector<int> bit_off; // 组 g 的 Fenwick 起点
vector<int> cnt; // 组 g 当前活跃点数
const int MAXN_SEG = 200000 * 4;
long long seg[MAXN_SEG]; // 线段树：结点覆盖的组区间内最大 y，空组为 -1
int groups; // 组数，线段树区间是 [1, groups]
// 组 g（1-based）的候选 y 个数
int bit_len(int g) {
return yoff[g] - yoff[g - 1];
}
void bit_add(int g, int idx, int delta) {
int base = bit_off[g];
int len = bit_len(g);
while (idx <= len) {
fenwick[base + idx] += delta;
idx += idx & -idx;
}
}
long long bit_sum(int g, int idx) {
int base = bit_off[g];
long long res = 0;
while (idx > 0) {
res += fenwick[base + idx];
idx -= idx & -idx;
}
return res;
}
// 组内找第 target 个活跃 y 的压缩下标（Fenwick 二进制提升）
int bit_kth(int g, long long target) {
int base = bit_off[g];
int len = bit_len(g);
int idx = 0;
int step = 1 << (31 - __builtin_clz(len)); // 不超过 len 的最大 2 的幂
while (step) {
int nxt = idx + step;
if (nxt <= len && fenwick[base + nxt] < target) {
idx = nxt;
target -= fenwick[base + nxt];
}
step >>= 1;
}
return idx + 1;
}
// 点更新：把第 pos 组的叶子值改成 value，并向上合并区间最大值
void seg_update(int p, int l, int r, int pos, long long value) {
if (l == r) {
seg[p] = value;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
seg_update(p << 1, l, mid, pos, value);
else
seg_update(p << 1 | 1, mid + 1, r, pos, value);
seg[p] = max(seg[p << 1], seg[p << 1 | 1]);
}
// 找最小的组号 g 使 start <= g 且第 g 组的最大 y > y；不存在返回 0
int first_x(int p, int l, int r, int start, long long y) {
if (r < start || seg[p] <= y) // 整段在起点左边，或整段最大值都够不到 y
return 0;
if (l == r)
return l;
int mid = (l + r) >> 1;
int res = first_x(p << 1, l, mid, start, y); // 先左后右，返回的组号自然最小
if (res)
return res;
return first_x(p << 1 | 1, mid + 1, r, start, y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
set<pair<long long, long long>> points;
for (int i = 0; i < n; i++) {
string s;
cin >> s >> ox[i] >> oy[i];
op[i] = s[0];
if (op[i] == 'a')
points.insert({ox[i], oy[i]});
}
// 坐标压缩：x 升序去重，每个 x 的 y 升序去重
for (auto &p : points) {
if (xs.empty() || xs.back() != p.first) {
xs.push_back(p.first);
yoff.push_back((int)ys.size());
}
ys.push_back(p.second);
}
yoff.push_back((int)ys.size());
groups = (int)xs.size();
bit_off.assign(groups + 2, 0); // bit_off[g]：组 g 的 Fenwick 在共享数组里的起点，1-based
for (int g = 1; g <= groups; g++)
bit_off[g + 1] = bit_off[g] + bit_len(g) + 1;
fenwick.assign(bit_off[groups + 1], 0);
cnt.assign(groups + 1, 0);
fill(seg, seg + 4 * groups + 4, -1); // 初始一个点都没有，所有组都按空组算
for (int i = 0; i < n; i++) {
if (op[i] != 'f') {
int g = (int)(lower_bound(xs.begin(), xs.end(), ox[i]) - xs.begin()) + 1; // 组号从 1 开始
int s = yoff[g - 1], e = yoff[g];
int pos = (int)(lower_bound(ys.begin() + s, ys.begin() + e, oy[i]) - ys.begin()) - s + 1;
int delta = (op[i] == 'a') ? 1 : -1;
bit_add(g, pos, delta);
cnt[g] += delta;
long long maxy = -1;
if (cnt[g] > 0)
maxy = ys[s + bit_kth(g, cnt[g]) - 1]; // 第 cnt 个即最大
seg_update(1, 1, groups, g, maxy);
continue;
}
// find：先找第一个 x 更大的可行组
int start = (int)(upper_bound(xs.begin(), xs.end(), ox[i]) - xs.begin()) + 1;
int g = first_x(1, 1, groups, start, oy[i]);
if (g == 0) {
cout << "-1\n";
continue;
}
int s = yoff[g - 1], e = yoff[g];
int pos = (int)(upper_bound(ys.begin() + s, ys.begin() + e, oy[i]) - ys.begin()) - s;
long long target = bit_sum(g, pos) + 1; // 第一个严格大于 query_y 的活跃 y 的秩
long long ans_y = ys[s + bit_kth(g, target) - 1];
cout << xs[g - 1] << ' ' << ans_y << '\n';
}
return 0;
}import sys
from array import array
from bisect import bisect_left, bisect_right
input = sys.stdin.buffer.readline
request_count = int(input())
kinds = bytearray()
request_x = array("q")
request_y = array("q")
points = []
for _ in range(request_count):
operation, x, y = input().split()
kind = 0 if operation == b'add' else 1 if operation == b'remove' else 2
x, y = int(x), int(y)
kinds.append(kind)
request_x.append(x)
request_y.append(y)
if kind == 0:
points.append((x, y))
# 离线坐标压缩：x 升序去重后，组号 = 下标 + 1（与 main2.cpp 的 1-based 组号一致）
points.sort()
x_values_list = []
y_values_list = []
y_offsets_list = []
previous = None
for point in points:
if point == previous:
continue
x, y = point
if not x_values_list or x != x_values_list[-1]:
x_values_list.append(x)
y_offsets_list.append(len(y_values_list))
y_values_list.append(y)
previous = point
y_offsets_list.append(len(y_values_list))
del points
x_values = array("q", x_values_list)
y_values = array("q", y_values_list)
y_offsets = array("i", y_offsets_list)
del x_values_list, y_values_list, y_offsets_list
groups = len(x_values)
# 组 g（1-based）的候选 y 是 y_values[y_offsets[g-1] .. y_offsets[g]-1]
bit_offsets = array("i", [0]) * (groups + 2)
for group in range(1, groups + 1):
bit_offsets[group + 1] = bit_offsets[group] + (y_offsets[group] - y_offsets[group - 1]) + 1
fenwick = array("i", [0]) * bit_offsets[groups + 1]
counts = array("i", [0]) * (groups + 1)
segment = array("q", [-1]) * (4 * groups + 4)
def bit_length_of(group):
"""组 group 的候选 y 个数。"""
return y_offsets[group] - y_offsets[group - 1]
def bit_add(group, index, delta):
base = bit_offsets[group]
length = bit_length_of(group)
while index <= length:
fenwick[base + index] += delta
index += index & -index
def bit_sum(group, index):
base = bit_offsets[group]
result = 0
while index:
result += fenwick[base + index]
index -= index & -index
return result
def bit_kth(group, target):
"""组内找第 target 个活跃 y 的压缩下标（1-based）。"""
base = bit_offsets[group]
length = bit_length_of(group)
index = 0
step = 1 << (length.bit_length() - 1)
while step:
next_index = index + step
if next_index <= length and fenwick[base + next_index] < target:
index = next_index
target -= fenwick[base + index]
step >>= 1
return index + 1
def seg_update(node, left, right, pos, value):
"""点更新：把第 pos 组的叶子值改成 value，并向上合并区间最大值。"""
if left == right:
segment[node] = value
return
middle = (left + right) // 2
if pos <= middle:
seg_update(node * 2, left, middle, pos, value)
else:
seg_update(node * 2 + 1, middle + 1, right, pos, value)
segment[node] = max(segment[node * 2], segment[node * 2 + 1])
def first_x(node, left, right, start, y):
"""找最小的组号 g 使 start <= g 且第 g 组的最大 y > y；不存在返回 0。"""
if right < start or segment[node] <= y: # 整段在起点左边，或整段最大值都够不到 y
return 0
if left == right:
return left
middle = (left + right) // 2
result = first_x(node * 2, left, middle, start, y) # 先左后右，返回的组号自然最小
return result if result else first_x(node * 2 + 1, middle + 1, right, start, y)
answers = []
for kind, x, y in zip(kinds, request_x, request_y):
if kind < 2:
group = bisect_left(x_values, x) + 1 # 组号从 1 开始
start, end = y_offsets[group - 1], y_offsets[group]
position = bisect_left(y_values, y, start, end) - start + 1
delta = 1 if kind == 0 else -1
bit_add(group, position, delta)
counts[group] += delta
if counts[group]:
maximum = y_values[start + bit_kth(group, counts[group]) - 1]
else:
maximum = -1
seg_update(1, 1, groups, group, maximum)
continue
group = first_x(1, 1, groups, bisect_right(x_values, x) + 1, y)
if group == 0:
answers.append('-1')
continue
start, end = y_offsets[group - 1], y_offsets[group]
position = bisect_right(y_values, y, start, end) - start
target = bit_sum(group, position) + 1
answer_y = y_values[start + bit_kth(group, target) - 1]
answers.append(f'{x_values[group - 1]} {answer_y}')
sys.stdout.write('\n'.join(answers))复杂度
预处理 add/remove 是组内一次 Fenwick 更新 + 一次 kth 求最大 find 是一次单路下降 + 一次前缀和 + 一次 kth。总时间
复杂度对比
| 方案 | 组内容器 | 是否在线 | 每次操作 | 空间 | 关键代价 |
|---|---|---|---|---|---|
解法一 main.cpp |
std::set<int> |
是 | 平衡树结点开销、常数稍大 | ||
解法二 main2.cpp |
离线压缩 + Fenwick | 否 | 必须先读完输入；多一个 kth 定位 |
||
解法二 main2.py |
同上（array） |
否 | 同上；Python 下靠纯数组换常数 |
三份实现的渐进复杂度相同，拉开差距的是常数与前提条件。本题
总结
这道题的解法可以概括成一句话：二维的最左可行点查询，拆成「外层找最小可行的
几个值得记住的细节：
- 外层不能在「组内最大
」这个量上直接二分，因为它不单调；合法的判据是「区间最大值」，而它恰好就是线段树结点存的东西，于是二分可以整个搬进下降过程，把 压回 。 - 剪枝条件有两个，缺一个就退化：
管「这段无解」， 管「这段越界」。 - 内层容器可以自由替换——平衡树在线、Fenwick 离线省常数，两者的接口都只是「取最大」和「取第一个大于
的」，所以外层代码可以完全不动。 - 严格大于、严格右上都体现为
upper_bound与seg[p] <= y里的那个等号方向，改错一个符号就会把「共线」的点也算进答案。