程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 19D Points 線段樹+set

Codeforces 19D Points 線段樹+set

編輯：C++入門知識

題目鏈接：點擊打開鏈接

線段樹維護y值大於val的最小x值

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define inf 1000000010
#define ll int
#define N 200005
#define L(x) (x<<1)
#define R(x) (x<<1|1)
inline ll Mid(ll a,ll b){return (a+b)>>1;}
ll n;
struct node{
	ll x,y;
	node(ll a=0,ll b=0):x(a),y(b){}
	bool operator<(const node &a) const{
		if(a.x==x)
			return a.y>y;
		return a.x>x;
	}
	ll op;
}in[N];
setmyset;
set::iterator p;
struct Edge{
	int l, r, id;
	int maxx, lval;
	setst;
}tree[N<<4];
set::iterator pp;
setlisan;
void build(int l,int r,int id){
	tree[id].l =l ,tree[id].r =r;
	tree[id].maxx = tree[id].lval = -1;
	tree[id].st.clear();
	tree[id].st.insert(-1);
	if(l==r)return ;
	int mid = Mid(l,r);
	build(l,mid,L(id));
	build(mid+1,r,R(id));
}
void updata(ll pos, ll id, ll val, ll o){ // o = 1表示插入
	if(tree[id].l== tree[id].r) {
		if(o==1){
			tree[id].st.insert(val);
			tree[id].lval = tree[id].maxx = max(tree[id].maxx,val);			
			return ;
		}
		else tree[id].st.erase(val);
		pp = tree[id].st.end(); pp--;
		tree[id].lval = tree[id].maxx = *pp;
		return;
	}
	ll mid = Mid(tree[id].l,tree[id].r);
	if(midval)return tree[id].l;
	}
	ll mid = Mid(tree[id].l,tree[id].r);
	if(midmp;
int main(){
	ll x,y;
	while(~scanf("%d",&n)) {
		myset.clear();
		mp.clear();
		lisan.clear();
		for(ll i = 0; i < n; i++) {
			char s[10];scanf("%s",s);
			scanf("%d %d",&in[i].x,&in[i].y);
			lisan.insert(in[i].x);
			if(s[0]=='a')in[i].op = 1;
			else if(s[0]=='r')in[i].op=2;
			else in[i].op = 3;
		}
		ll siz = 1;
		for(pp=lisan.begin(); pp!=lisan.end(); pp++) {
			pos[siz] = *pp;
			mp.insert(pair(*pp,siz));
			siz++;
		}
		for(ll i = 0; i < n; i++)in[i].x = mp.find(in[i].x)->second;
		build(1,siz,1);
		for(ll i = 0; i < n; i++){
			x = in[i].x, y = in[i].y;
			if(in[i].op == 1){
				myset.insert(node(pos[x],y));
				updata(in[i].x,1,in[i].y,1);
			}
			else if(in[i].op == 2){
				myset.erase(node(pos[x],y));
				updata(in[i].x,1,in[i].y,0);
			}
			else {
				ll he = query(in[i].x+1,siz,1,in[i].y);
				if(he==-1){puts("-1");continue;}
				printf("%d %d\n",pos[he],myset.lower_bound(node(pos[he],in[i].y+1))->y);
			}
		}
	}
	return 0;
}