Points

题意

动态加入、删除点；查询严格右上方的点，要求先取最小 x，再取该 x 下最小 y。

思路

先读完所有操作，压缩所有可能出现的 x，并为每个 x 收集可能的 y。每个 x 组用 Fenwick 维护当前点，外层线段树保存该组当前最大 y。查询时在线段树中找第一个 x > query_x 且最大 y > query_y 的组，再用组内 Fenwick 的前缀计数定位第一个大于 query_y 的 y。

Python 知识

离线读取请求后用 sorted(set(...)) 和字典推导式完成坐标压缩。
Fenwick 的 kth 二进制提升可在计数树中找第 k 个活跃坐标。
bisect_right 表达严格大于边界，避免手写二分。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130import 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))

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)
bit_offsets = array("i", [0])
for group in range(groups):
    bit_offsets.append(bit_offsets[-1] + y_offsets[group + 1] - y_offsets[group] + 1)
fenwick = array("i", [0]) * bit_offsets[-1]
counts = array("i", [0]) * groups
size = 1
while size < groups:
    size <<= 1
segment = array("q", [-1]) * (2 * size)


def bit_add(group, index, delta):
    base = bit_offsets[group]
    length = y_offsets[group + 1] - y_offsets[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):
    base = bit_offsets[group]
    length = y_offsets[group + 1] - y_offsets[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 set_leaf(index, value):
    node = size + index
    segment[node] = value
    node //= 2
    while node:
        segment[node] = max(segment[node * 2], segment[node * 2 + 1])
        node //= 2


def first_x(node, left, right, start, y):
    if right <= start or segment[node] <= y:
        return -1
    if right - left == 1:
        return left
    middle = (left + right) // 2
    result = first_x(node * 2, left, middle, start, y)
    return result if result != -1 else first_x(node * 2 + 1, middle, right, start, y)


answers = []
for kind, x, y in zip(kinds, request_x, request_y):
    if kind < 2:
        group = bisect_left(x_values, x)
        start, end = y_offsets[group], y_offsets[group + 1]
        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
        set_leaf(group, maximum)
        continue
    group = first_x(1, 0, size, bisect_right(x_values, x), y)
    if group == -1 or group >= groups:
        answers.append('-1')
        continue
    start, end = y_offsets[group], y_offsets[group + 1]
    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]} {answer_y}')
sys.stdout.write('\n'.join(answers))

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * 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-07-16 23:46
 * update_at: 2026-07-16 23:46
 */
#include <bits/stdc++.h>
using namespace std;

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

    return 0;
}

复杂度

外层查找、组内 Fenwick 和坐标二分均为 O(log n)，所以每个操作 O(log n)，空间 O(n)。

总结

二维动态查询可以拆成“外层找最小可行 x，内层找最小可行 y”；离线坐标压缩让两层结构都能使用数组。

目录

题意

思路

Python 知识

代码

复杂度

总结