CodeforcesBeta Round #19 D. Points
题意:有三种操作“add x y”往平面上添加(x,y)这个点,"remove x y",将平面上已经存在的点(x,y)删除,“find x y”找出平面上坐标严格大于(x,y)的点,如果有多个点找x最小的,再找y最小的。
思路:将所有点 x 坐标离散化,然后按照新的坐标建一个线段树。对于每一个坐标x,维护一个set,add操作在相应的set里加入y,remove操作在相应的set里减去y。再有一个sum[]数组来维护最值。每次add、remove操作通过pushup操作更新最值。find操作只要找到相应的点即可。
代码:
#include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, n) for (int i = 0; i < n; i++) #define debug puts("===============") typedef long long ll; using namespace std; int n; const int maxn = 210000; int x[maxn], y[maxn], op[maxn], index[maxn], dis[maxn]; char str[11]; int discrete(int x[], int index[], int dis[], int n) { int cpy[n]; memcpy(cpy, x, sizeof(cpy)); sort(cpy, cpy + n); int tot = unique(cpy, cpy + n) - cpy; for (int i = 0; i < n; i++) { dis[i] = lower_bound(cpy, cpy + tot, x[i]) - cpy; index[dis[i]] = x[i]; } return tot; } #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 set<int> s[maxn]; int mx[maxn << 2]; void build(int l, int r, int rt) { mx[rt] = 0; if (l == r) { s[l].clear(); return ; } int m = (l + r) >> 1; build(lson); build(rson); } int pushup(int rt) { mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]); } void add(int pos, int x, int l, int r, int rt) { if (l == r) { s[l].insert(x); mx[rt] = max(mx[rt], x); return ; } int m = (l + r) >> 1; if (pos <= m) add(pos, x, lson); else add(pos, x, rson); pushup(rt); } void remove(int pos, int x, int l, int r, int rt) { if (l == r) { s[l].erase(x); mx[rt] = (s[l].empty() ? 0 : *--s[l].end()); return ; } int m = (l + r) >> 1; if (pos <= m) remove(pos, x, lson); else remove(pos, x, rson); pushup(rt); } pair<int, int> find(int pos, int x, int l, int r, int rt) { if (mx[rt] < x || r < pos) return make_pair(l, -1); if (l == r) return make_pair(l, *s[l].lower_bound(x)); int m = (l + r) >> 1; pair<int, int> res = find(pos, x, lson); if (res.second != -1) return res; else return find(pos, x, rson); } int main () { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s%d%d", str, x + i, y + i); if (str[0] == 'a') op[i] = 1; else if (str[0] == 'r') op[i] = 2; else op[i] = 3; } int m = discrete(x, index, dis, n); build(0, m - 1, 1); for (int i = 0; i < n; i++) { if (op[i] == 1) { add(dis[i], y[i], 0, m - 1, 1); } else if (op[i] == 2) { remove(dis[i], y[i], 0, m - 1, 1); } else { pair<int, int> res = find(dis[i] + 1, y[i] + 1, 0, m - 1, 1); if (res.second == -1) puts("-1"); else printf("%d %d\n", index[res.first], res.second); } } return 0; }