CF 评测记录

#include <iostream>
#include <algorithm>
#include <set>
#include <cstring>
#define lc (x << 1)
#define rc (x << 1 | 1)
#define set_it(x) set<x>::iterator
using namespace std;

const int MAXN = 2e5 + 5;
int n, szx, szy, x[MAXN], y[MAXN], X[MAXN], Y[MAXN], xx[MAXN], yy[MAXN];
int maxx[MAXN], tr[MAXN << 2], maxp[MAXN << 2];
// maxx[i]表示横坐标为i的点的y的最大值 
// tr[i]表示节点i管辖区间maxx的最大值 
string op[MAXN];
set<int> s[MAXN]; // s[i]存储横坐标为i的点 

void recover(int x, int l, int r)
{
	if(tr[lc] >= tr[rc]) tr[x] = tr[lc], maxp[x] = maxp[lc];
	else tr[x] = tr[rc], maxp[x] = maxp[rc];
}
void build(int x, int l, int r)
{
	if(l == r)
	{
		tr[x] = -1, maxp[x] = -1;
		return ;
	}
	int mid = l + r >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	recover(x, l, r);
}
void update(int x, int l, int r, int q, int k)
{ // 将q的maxx改为k，删除则改为-1 
	if(l == q && r == q)
	{
		tr[x] = k, maxp[x] = k;
		return ;
	}
	int mid = l + r >> 1;
	update(lc, l, mid, q, k);
	update(rc, mid + 1, r, q, k);
	recover(x, l, r);
}
int calc(int x, int l, int r, int qx, int qy)
{
	if(l == r)
	{
		if(tr[x] > qy) return l;
		return -1;
	}
	int mid = l + r >> 1, res = -1;
	if(qx <= mid && tr[lc] > qy) res = calc(lc, l, mid, qx, qy);
	if(~res) return res;
	if(tr[rc] > qy) return calc(rc, mid + 1, r, qx, qy);
	return -1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n;
	memset(maxx, -1, sizeof maxx);
	for(int i = 1; i <= n; i++) cin >> op[i] >> x[i] >> y[i];
	for(int i = 1; i <= n; i++) X[i] = x[i], Y[i] = y[i];
	sort(X + 1, X + n + 1), sort(Y + 1, Y + n + 1);
	szx = unique(X + 1, X + n + 1) - X - 1;
	szy = unique(Y + 1, Y + n + 1) - Y - 1;
	for(int i = 1; i <= n; i++)
	{
		int pos = lower_bound(X + 1, X + szx + 1, x[i]) - X;
		xx[pos] = x[i], x[i] = pos;
	}
	for(int i = 1; i <= n; i++)
	{
		int pos = lower_bound(Y + 1, Y + szy + 1, y[i]) - Y;
		yy[pos] = y[i], y[i] = pos;
	}
	build(1, 1, szx);
	for(int i = 1; i <= n; i++)
	{
		if(op[i] == "add")
		{
			if(y[i] > maxx[x[i]]) update(1, 1, szx, x[i], maxx[x[i]] = y[i]);
			s[x[i]].insert(y[i]);
		}
		if(op[i] == "remove")
		{
			if(y[i] == maxx[x[i]])
				if(s[x[i]].size() == 1) update(1, 1, szx, x[i], maxx[x[i]] = -1);
				else
				{
					set_it(int) it = prev(s[x[i]].end(), 2);
					update(1, 1, szx, x[i], maxx[x[i]] = *it);
				}
			s[x[i]].erase(y[i]);
		}
		if(op[i] == "find")
		{
            int pos = calc(1, 1, szx, x[i] + 1, y[i]);
            if(pos == -1) cout << -1 << endl;
            else cout << x[xx[x[pos]]] << ' ' << y[yy[y[*s[x[pos]].upper_bound(y[i])]]] << endl;
		}
	}
	
	return 0;
}