CF 19D Points

题目描述

https://codeforces.com/problemset/problem/19/D

简要题意：在二维平面上维护一个点集 $S$，现在有 $m$ 次操作，操作有三种，第一种操作给定 $(x,y)$，表示在 $S$ 中加入点 $(x,y)$；第二种操作给定 $(x,y)$，表示在 $S$ 中删除点 $(x,y)$；第三种操作给定 $(x,y)$，求满足 $x’>x,y’>y$ 的最小的 $x’$，如果最小的 $x’$ 不唯一，则选择 $y’$ 最小的

Solution

离散化之后按照 $x$ 建线段树，每次查询相当于在线段树区间 $[x+1,cnt]$ 上最小 $i$ 使得，$y_i>y$，且 $y_i$ 最小

对于一个 $x$，我们用一个 $set$ 把横坐标是 $x$ 的 $y$ 都扔进去，那么我们只需要找到对应 $i$ 即可

这个东西可以在线段树上二分，且时间复杂度为 $O(\log n)$

实际上我们会将每次查询的线段分成 $O(\log n)$ 个线段，对于每个线段的直接判断是 $O(1)$，只有一个线段会下到叶节点

时间复杂度 $O(n\log n)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#define maxn 200010
using namespace std;

int n, m;

struct Query {
    int opt, x, y;
} Q[maxn]; 

int b[maxn], cnt; 
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = Q[i].x;
    sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) Q[i].x = lower_bound(b + 1, b + cnt + 1, Q[i].x) - b;
}

#define lc i << 1
#define rc i << 1 | 1
int T[maxn * 4];
inline void maintain(int i) { T[i] = max(T[lc], T[rc]); }

void update(int i, int l, int r, int k, int v) {
    if (l == r) return (void) (T[i] = v);
    int m = l + r >> 1;
    if (k <= m) update(lc, l, m, k, v);
    else update(rc, m + 1, r, k, v);
    maintain(i); 
}

int query(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L || T[i] <= v) return 0;
    if (l == r) return T[i] > v ? l : 0;
    int m = l + r >> 1, p = query(lc, l, m, L, R, v);
    if (!p) return query(rc, m + 1, r, L, R, v);
    else return p; 
} 

set<int> S[maxn]; 
inline void solve_1(int o) {
    int x = Q[o].x, y = Q[o].y; S[x].insert(y);
    update(1, 1, cnt, x, *--S[x].end()); 
}

inline void solve_2(int o) {
    int x = Q[o].x, y = Q[o].y; S[x].erase(y);
    if (S[x].empty()) update(1, 1, cnt, x, 0);
    else update(1, 1, cnt, x, *--S[x].end());
}

inline void solve_3(int o) {
    int x = Q[o].x, y = Q[o].y, p = query(1, 1, cnt, x + 1, cnt, y);
    if (!p) return (void) (puts("-1")); 
    printf("%d %d\n", b[p], *S[p].upper_bound(y));
}


int main() {
    cin >> n; 
    for (int i = 1; i <= n; ++i) {
        char s[5]; scanf("%s%d%d", s, &Q[i].x, &Q[i].y);
        if (s[0] == 'a') Q[i].opt = 1;
        else if (s[0] == 'r') Q[i].opt = 2;
        else Q[i].opt = 3;
    } init_hash();
    for (int i = 1; i <= n; ++i) {
        int opt = Q[i].opt;
        switch (opt) {
        case 1 : solve_1(i); break;
        case 2 : solve_2(i); break;
        case 3 : solve_3(i); break;
        }
    }
    return 0;
}