CF19D Points

发表于 分类于 阅读次数： Waline： 本文字数： 700 阅读时长 ≈ 2 分钟

考点

  • 线段树

题解

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 50;
#define lc p << 1
#define rc p << 1 | 1
int n, dis[maxn];
// 线段树
// mx：区间最大值
// st：每个叶子节点保存的set，set保存相同x上的y
int mx[maxn << 2];
set<int> st[maxn << 2];

struct {
  int x, y;
  string op;
} req[maxn];

// 0：新增
// 1：删除
void update(int p, int l, int r, int op, int x, int v) {
  if (l == r && x == l) {
    if (!op)
      st[p].emplace(v);
    else
      st[p].erase(v);
    mx[p] = st[p].empty() ? 0 : *(st[p].rbegin());
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) update(lc, l, mid, op, x, v);
  if (x > mid) update(rc, mid + 1, r, op, x, v);
  mx[p] = max(mx[lc], mx[rc]);
}

// 二分，大于v的最小x
pair<int, int> ask(int p, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R && l == r) {
    if (mx[p] > v) return {l, p};
    return {-1, -1};
  }
  int mid = (l + r) >> 1;
  pair<int, int> ans(-1, -1);
  if (L <= mid && mx[lc] > v) ans = ask(lc, l, mid, L, R, v);
  if (ans.first != -1) return ans;
  if (R > mid && mx[rc] > v) ans = ask(rc, mid + 1, r, L, R, v);
  return ans;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int q;
  cin >> q;
  // 离散化
  for (int i = 1; i <= q; ++i) {
    cin >> req[i].op >> req[i].x >> req[i].y;
    dis[++n] = req[i].x;
  }
  sort(dis + 1, dis + 1 + n);
  n = unique(dis + 1, dis + 1 + n) - 1 - dis;
  for (int i = 1; i <= q; ++i) {
    int x = lower_bound(dis + 1, dis + 1 + n, req[i].x) - dis;
    if (req[i].op[0] == 'a') {
      update(1, 1, n, 0, x, req[i].y);
    } else if (req[i].op[0] == 'r') {
      update(1, 1, n, 1, x, req[i].y);
    } else {
      pair<int, int> ans = ask(1, 1, n, x + 1, n, req[i].y);
      if (ans.first == -1)
        cout << -1 << endl;
      else
        cout << dis[ans.first] << " "
             << *(st[ans.second].lower_bound(req[i].y + 1)) << endl;
    }
  }
  return 0;
}

思路

线性复杂度肯定不行，那么x、y两轴的搜索必须都是logn复杂度，假设要找(A, B)

将所有请求读入后，先对x轴进行离散化，得到n个排名。

对每个x开一个set，以保存该x轴上的y，不仅仅能得到y的极大值mx，

还可使用lower_bound函数以logn的复杂度，检索在同一x坐标的情况下，第一个大于等于B + 1的y。

取最大值是有单调不减的性质的，固定左端点时，右端点一直向右移动，区间内的极大值维持单调不减，

所以开一个线段树，把每个x作为叶子节点，叶子节点的值就设为x对应set的极大值mx，然后区间取极大值，

对线段树进行二分，在[A + 1, n]的x范围内，找到y大于B的最小x：

  1. 如果左孩子的y极大值大于B，向左孩子搜索（因为要找最小，肯定先走左孩子）
  2. 左孩子如果得到答案，就直接返回
  3. 否则向右孩子走

二分后得到的x，就是满足y一定存在大于B条件的最小x