D. Points
- 題意：在笛卡爾坐标系上有 n 個操作，添加點 (x, y)，删除點 (x, y) 和查詢點 (x, y) 的最近的右上角的點 (x1, y1) 【在保證(x1 - x)最小的基礎上尋找(y1-y)最小】
思路1：橫縱坐标的範圍很大，是以我們對橫縱坐标離散化，然後對離散後的橫坐标用線段樹維護，線段樹維護橫坐标 x 對應豎直線上點的個數。我們用 set 存儲橫坐标 x 對應豎直線上點的集合。點的添加和删除操作直接跑到葉子節點對 set 進行insert或者erase即可。查詢點 (x, y) 操作的時候我們可以通過查詢線段樹找到橫坐标大于 x 并且 x 對應集合中有縱坐标大于 y 的最小的 x 。找到x之後我們就從x的集合中找到第一個縱坐标大于y的點即可。
我們線段樹維護區間最大的縱坐标點值，當查詢時判斷區間中是否有大于y的縱坐标點。如果左區間有可行點，那麼一定比右區間的可行點優。當左區間沒有可行點時再考慮右區間的可行點。這樣可以保證我們最多隻跑兩個葉子節點，控制複雜度。
線段樹 + set維護縱坐标點
-
分析
單次add/remove: O(2logn)//葉子節點一個log + set的插入或删除一個log
單次find：O(2logn)+O(logn)//最多跑兩個葉子節點->兩個log + set二分找縱坐标一個log
總複雜度：O(3nlogn)
不長記性又寫cout，TTTTTTTTT!!!
#include <bits/stdc++.h>
#define MID (l + r) >> 1
#define lsn rt << 1
#define rsn rt << 1 | 1
#define Lson lsn, l, mid
#define Rson rsn, mid + 1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
using namespace std;
typedef long long ll;
const int maxN = 200005;
int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = -f; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int n;
int discx[maxN], discy[maxN];
struct OP {
string op;
int x, y;
}_op[maxN];
int tree[maxN << 2], maxy[maxN << 2]; //維護區間y最大值
set<int>st[maxN]; //st[i]: 縱軸x = i上點的集合
enum lalala{add, remo};
void pushup(int rt) {
tree[rt] = tree[lsn] + tree[rsn];
maxy[rt] = max(maxy[lsn], maxy[rsn]);
}
void update(int rt, int l, int r, int xx, int yy, lalala ar) { //縱軸x=xx上點的個數加1，點增加一個yy
if(l == r) {
switch (ar) {
case add: {
++ tree[rt], st[l].insert(yy);
maxy[rt] = *st[l].rbegin();
break;
}
case remo: {
-- tree[rt], st[l].erase(yy);
if(st[l].empty()) maxy[rt] = 0;
else maxy[rt] = *st[l].rbegin();
break;
}
}
return ;
}
int mid = MID;
if(xx <= mid) update(Lson, xx, yy, ar);
else update(Rson, xx, yy, ar);
pushup(rt);
}
int query(int rt, int l, int r, int xx, int yy) { //找到[l, r]中第一個大于xx的并且存在縱坐标點大于yy的集合
if(!tree[rt] || maxy[rt] <= yy) {
return -1;
}
if(l == r) {
if(l <= xx) return -1;
return l;
}
int mid = MID;
if(mid > xx) {
int lans = query(Lson, xx, yy);
if(lans == -1) return query(Rson, xx, yy);
return lans;
} else {
return query(Rson, xx, yy);
}
}
int main() {
n = read();
for(int i = 0; i < n; ++ i ) {
string op; cin >> op;
int xx = discx[i] = read();
int yy = discy[i] = read();
_op[i] = OP{op, xx, yy};
}
sort(discx, discx + n);
int UPX = unique(discx, discx + n) - discx; //離散化後不同x的個數
sort(discy, discy + n);
int UPY = unique(discy, discy + n) - discy; //離散化後不同y的個數
//更新坐标為離散化後的坐标
for(int i = 0; i < n; ++ i ) {
_op[i].x = lower_bound(discx, discx + UPX, _op[i].x) - discx;
_op[i].y = lower_bound(discy, discy + UPY, _op[i].y) - discy;
}
for(int i = 0; i < n; ++ i ) {
switch (_op[i].op[0]) {
case 'a': update(1, 0, UPX - 1, _op[i].x, _op[i].y, add); break;
case 'r': update(1, 0, UPX - 1, _op[i].x, _op[i].y, remo); break;
case 'f': {
int xx = _op[i].x, yy = _op[i].y;
xx = query(1, 0, UPX - 1, xx, yy);
if(xx == -1) { printf("-1\n"); /*fflush(stdout);*/ continue; }
yy = *st[xx].upper_bound(_op[i].y);
printf("%d %d\n", discx[xx], discy[yy]);
// fflush(stdout);
break;
}
}
}
return 0;
}
思路2：我們對x*(1e9)+y的離散化的值建立線段樹，更新點直接更新x*(1e9)+y的離散化值即可。查詢點的時候，我們先二分找到(x+1)*(1e9)的點，也就是找到了可能可行的最小的橫坐标ansx。然後我們再找到ansx到離散化的右邊界中合法的點。
思路就是這麼個思路，就是實作起來有點繞，也可能是了解不深刻，反正寫了很久還調了很久，對于各個變量和參數的意義和調用都需要想清楚。
分析：
單次更新點：O(logn)
單次查詢：O(logn + 2logn) //二分找最小x，線段樹最多兩個葉子節點找合法x, y
總複雜度：O(3nlogn)
但是這個做法比第一種快，就快到了更新點。
#include <bits/stdc++.h>
#define MID (l + r) >> 1
#define lsn rt << 1
#define rsn rt << 1 | 1
#define Lson lsn, l, mid
#define Rson rsn, mid + 1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
using namespace std;
typedef long long ll;
const int maxN = 200005;
const ll c = 1e9;
int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = -f; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int n;
struct node{
char op; ll x, y; int xy;
}mem[maxN];
ll disc[maxN], UP;
int tree[maxN << 2]; //離散化後的xc+y
int maxY[maxN << 2]; //原y
enum OP{add, remo};
void pushup(int rt) {
tree[rt] = tree[lsn] + tree[rsn];
maxY[rt] = max(maxY[lsn], maxY[rsn]);
}
void update(int rt, int l, int r, int x, int y, OP op) {
if(l == r) {
switch (op) {
case add: ++ tree[rt]; maxY[rt] = y; break;
case remo: -- tree[rt]; maxY[rt] = 0; break;
}
return ;
}
int mid = MID;
if(mid < x) update(Rson, x, y, op);
else update(Lson, x, y, op);
pushup(rt);
}
pair<int, int> query(int rt, int l, int r, int ql, int qr, int yy) {
if(!tree[rt] || maxY[rt] <= yy) return make_pair(-1, -1);
if(l == r) {
if(maxY[rt] <= yy) return make_pair(-1, -1);
return make_pair(disc[l] / c, maxY[rt]);
}
int mid = MID;
if(ql > mid) return query(QR, yy);
else if(qr <= mid) return query(QL, yy);
else {
pair<int, int> lans = query(QL, yy);
if(lans == make_pair(-1, -1)) return query(QR, yy);
else return lans;
}
}
int main() {
n = read();
for(int i = 0; i < n; ++ i ) {
string op; cin >> op;
ll x = read(), y = read();
mem[i] = {op[0], x, y, 0};
disc[i] = x * c + y;
}
sort(disc, disc + n);
UP = unique(disc, disc + n) - disc;
for(int i = 0; i < n; ++ i ) {
mem[i].xy = lower_bound(disc, disc + UP, mem[i].x * c + mem[i].y) - disc;
}
for(int i = 0; i < n; ++ i ) {
switch (mem[i].op) {
case 'a': update(1, 0, UP - 1, mem[i].xy, mem[i].y, add); break;
case 'r': update(1, 0, UP - 1, mem[i].xy, mem[i].y, remo); break;
case 'f':
int xx = lower_bound(disc, disc + UP, (mem[i].x + 1) * c) - disc;
if(xx == UP) { printf("-1\n"); /*fflush(stdout);*/ continue; }
pair<int, int >ans = query(1, 0, UP - 1, xx, UP - 1, mem[i].y);
if(ans == make_pair(-1, -1)) { printf("-1\n"); /*fflush(stdout);*/ continue; }
printf("%d %d\n", ans.first, ans.second);
// fflush(stdout);
break;
}
}
return 0;
}
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)