Codeforces 19D Points：樹狀數組與 Set 結合解決動態最近點查詢

題目大意

支援三種操作：添加點、刪除點、查詢給定 (x, y) 右上方最近的點。坐標範圍大，需離散化。

解法核心

將 y 座標離散化，建立樹狀數組（Fenwick Tree），每個節點維護一個 set<pair<int,int>> 存儲該區間內的點。添加/刪除點時，沿樹狀數組更新對應 set；查詢時，從 y+1 向上累加 set，並在合併集合中用 lower_bound 找到 x 方向最近的點。

關鍵代碼

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int maxn = 200005;
const int INF = 0x3f3f3f3f;
#define lowbit(x) ((x)&(-x))
typedef pair<int,int> pii;
typedef set<pii>::iterator iter;
int N, M, pos[maxn];
set<pii> fenw[maxn];
struct Cmd {
    int x, y; char op[10];
    void read() { scanf("%s%d%d", op, &x, &y); }
    void add() {
        for (int i = maxn - y; i < maxn; i += lowbit(i))
            fenw[i].insert(make_pair(x, y));
    }
    void del() {
        for (int i = maxn - y; i < maxn; i += lowbit(i))
            fenw[i].erase(make_pair(x, y));
    }
    void find() {
        pii ans(INF, INF);
        for (int i = maxn - y - 1; i; i -= lowbit(i)) {
            iter it = fenw[i].lower_bound(make_pair(x + 1, y));
            if (it != fenw[i].end()) ans = min(ans, *it);
        }
        if (ans == make_pair(INF, INF)) printf("-1\n");
        else printf("%d %d\n", ans.first, pos[ans.second]);
    }
    void solve() {
        if (op[0] == 'a') add();
        else if (op[0] == 'r') del();
        else find();
    }
} p[maxn];
void init() {
    M = 0; scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        p[i].read(); pos[i] = p[i].y;
    }
    sort(pos + 1, pos + 1 + N);
    M = unique(pos + 1, pos + 1 + N) - (pos + 1);
    for (int i = 1; i <= N; i++)
        p[i].y = lower_bound(pos + 1, pos + 1 + M, p[i].y) - pos;
}
int main() { init(); for (int i = 1; i <= N; i++) p[i].solve(); return 0; }

複雜度

每次操作 O(log² N)，空間 O(N log N)，滿足 2×10⁵ 操作限制。