[题解] CF19D Points

CF19D Points

在一个笛卡尔坐标系中，定义三种操作:

1. add x y：在坐标系上标记一个点 \((x, y)\)，保证 \((x, y)\) 在添加前不在坐标系上。

2. remove x y：移除点 \((x, y)\)，保证 \((x, y)\) 在移除前已在坐标系上。

3. find x y：找到所有已标记的 \((x', y')\)，需满足 \(x' > x\)，\(y' > y\)，输出其中 \(x'\) 最小的点。如果答案不唯一，则取 \(y'\) 最小的点。如果没有满足要求的 \((x', y')\)，输出 \(-1\)。

现给定 \(n\) 个操作，对于每个 find 操作，输出结果。

数据保证 \(n \leq 2 \times 10^5\)，\(0 \leq x, y \leq 10^9\)。

\(0 \leq x, y \leq 10^9\)？离散化取之！

添加删除一个点？set取之！

【操作三】？线段树套set取之！

离散化后，线段树套set，在外层线段树上二分找答案（查询时分讨一下）即可!

CODE:

int n;

struct node{
	string s;
	int x,y;
};node q[N<<1];

int b[N<<1],len,cnt;

set<int> s[N<<1];

int tree[N<<3];

void modify(int p,int l,int r,int pos,int val){
	if(l==r){
		tree[p]=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid){
		modify(p<<1,l,mid,pos,val);
	}
	else{
		modify(p<<1|1,mid+1,r,pos,val);
	}
	tree[p]=max(tree[p<<1],tree[p<<1|1]);
}

int query(int p,int l,int r,int x,int y,int val){
	if(tree[p]<=val || y<l || x>r){
		return -1;
	}
	if(l==r){
		return l;
	}
	int mid=(l+r)>>1;
	int res=query(p<<1,l,mid,x,y,val);
	if(~res){
		return res;
	}
	return query(p<<1|1,mid+1,r,x,y,val);
}

inline void solve(){
	ios::sync_with_stdio(NULL);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n;
	rep(i,1,n,1){
		cin>>q[i].s>>q[i].x>>q[i].y;
		b[++cnt]=q[i].x;
		b[++cnt]=q[i].y;
	}
	sort(b+1,b+cnt+1);
	len=unique(b+1,b+cnt+1)-b-1;
	rep(i,1,n,1){
		q[i].x=lower_bound(b+1,b+len+1,q[i].x)-b;
		q[i].y=lower_bound(b+1,b+len+1,q[i].y)-b;
	}
	rep(i,1,n,1){
		if(q[i].s[0]=='a'){
			s[q[i].x].insert(q[i].y);
			modify(1,1,len,q[i].x,*(--s[q[i].x].end()));
		}
		else{
			if(q[i].s[0]=='r'){
				s[q[i].x].erase(q[i].y);
				if(!s[q[i].x].size()){
					modify(1,1,len,q[i].x,0);
				}
				else{
					modify(1,1,len,q[i].x,*(--s[q[i].x].end()));
				}
			}
			else{
				int pos=query(1,1,len,q[i].x+1,len,q[i].y);
				if(pos==-1){
					cout<<-1<<'\n';
				}
				else{
					cout<<b[pos]<<" "<<b[*s[pos].upper_bound(q[i].y)]<<'\n';
				}
			}
		}
	}
}