CF 19D 线段树+set压缩坐标轴+离散化map
题意：
n个操作，在200000*200000的平面上加删点
find 严格在坐标右上角，x最小，再y最小的点
线段树做，区间为离散化后的 X轴坐标 ，维护区间点数 和 最小的 y 值 ( 维护最小y值是重要优化 )
#include <stdio.h>#include <string.h>#include <queue>#include <set>#include <functional>#include <map>#define N 201000#define L(x) (x<<1)#define R(x) (x<<1|1)#define Mid(x,y) ((x+y)>>1)#define ll intusing namespace std;inline ll Max(ll a, ll b){ return a>b?a:b;}inline ll Min(ll a, ll b){ return a<b?a:b;}int Point[N];map<int, int> mymap;vector<int>G;struct node{int l,r;int num;int maxy;}tree[N*4];set<int> treeset[N];set<int> ::iterator p;void build( int l, int r, int id){tree[id].l = l, tree[id].r = r;tree[id].num = 0;tree[id].maxy = 0;if(l==r)return ;int mid = Mid(l, r);build(l, mid, L(id));build(mid+1, r, R(id));}void insert(int pos, int id, int data, bool add){// add = true 插入data =false 删除dataif(tree[id].l == tree[id].r){if(add)treeset[pos].insert(data);else treeset[pos].erase(data);tree[id].num = treeset[pos].size();if(tree[id].num)tree[id].maxy = *treeset[pos].rbegin();else tree[id].maxy = 0;return ;}int mid = Mid(tree[id].l, tree[id].r);if(pos <= mid)insert(pos, L(id), data, add);else insert(pos, R(id), data, add);tree[id].num = tree[L(id)].num + tree[R(id)].num;tree[id].maxy =Max( tree[L(id)].maxy , tree[R(id)].maxy);}int query(int l, int r, int y, int id){if( tree[id].l == tree[id].r ){if(tree[id].num){p = treeset[ tree[id].l ].upper_bound(y);if(p != treeset[ tree[id].l ].end() ){printf("%d ", Point[ tree[id].l ]);return *p;}}return -1;}if( l == tree[id].l && tree[id].r == r){if(tree[id].num == 0 || tree[id].maxy <= y)return -1;}int mid = Mid(tree[id].l , tree[id].r);if(r <= mid) return query(l, r, y, L(id));if(mid < l) return query(l, r, y, R(id));int treey =query(l, mid, y, L(id));if(treey > y) return treey;return query(mid+1, r, y, R(id));}struct QUE{char c;int u,v;}que[N];set<int> tempset;void Input(int n){int u,v; char s[10];tempset.clear();mymap.clear();for(int i = 1; i <= n; i++){scanf("%s %d %d", s, &u, &v);que[i].c = s[0], que[i].u = u, que[i].v = v;tempset.insert(u);}p = tempset.begin();int size = tempset.size();for(int i = 1; i <= size ; i++,p++){mymap.insert(pair<int, int>(*p, i));Point[i] = *p;}}int go(int x){return mymap.find(x) -> second;}int main(){int n;char s[10];while(~scanf("%d",&n)){for(int i = 1; i<=200001; i++)treeset[i].clear();build(1,200001,1);Input(n);for(int i = 1; i<=n; i++){int u = que[i].u, v = que[i].v;if(que[i].c == 'a')insert(go(u),1,v,1);else if(que[i].c == 'r')insert(go(u),1,v,0);else if(que[i].c == 'f')printf("%d\n", query(go(u)+1, 200001, v, 1));}}return 0;}/* 7add 1 1add 3 4find 0 0remove 1 1find 0 0add 1 1find 0 0ans:1 13 41 113add 5 5add 5 6add 5 7add 6 5add 6 6add 6 7add 7 5add 7 6add 7 7find 6 6remove 7 7find 6 6find 4 4ans:7 7-15 510add 5 7add 2 1add 8 8add 5 10add 2 5find 7 5find 8 3find 2 2find 5 4find 2 6ans:8 8-15 78 85 7*/