Codeforces Beta Round #19 D. Points

Description

Pete and Bob invented a new interesting game. Bob takes a sheet of paper and locates a Cartesian coordinate system on it as follows: point (0, 0) is
located in the bottom-left corner, Ox axis is directed right, Oy axis is directed up. Pete gives Bob requests of three types:

add x y — on the sheet of paper Bob marks a point with coordinates (x, y). For each request of this type it's guaranteed that point(x, y) is
not yet marked on Bob's sheet at the time of the request.
remove x y — on the sheet of paper Bob erases the previously marked point with coordinates (x, y). For each request of this type it's guaranteed
that point (x, y) is already marked on Bob's sheet at the time of the request.
find x y — on the sheet of paper Bob finds all the marked points, lying strictly above and strictly to the right of point (x, y). Among these
points Bob chooses the leftmost one, if it is not unique, he chooses the bottommost one, and gives its coordinates to Pete.

Bob managed to answer the requests, when they were 10, 100 or 1000, but when their amount grew up to 2·10⁵,
Bob failed to cope. Now he needs a program that will answer all Pete's requests. Help Bob, please!

Input

The first input line contains
number n (1 ≤ n ≤ 2·10⁵)
— amount of requests. Then there follow n lines
— descriptions of the requests.add x y describes
the request to add a point, remove x y —
the request to erase a point, find x y —
the request to find the bottom-left point. All the coordinates in the input file are non-negative and don't exceed 10⁹.

Output

For
each request of type find x y output
in a separate line the answer to it — coordinates of the bottommost among the leftmost marked points, lying strictly above and to the right of point (x, y).
If there are no points strictly above and to the right of point (x, y),
output -1.

Sample
Input

Input

7

add 1 1

add 3 4

find 0 0

remove 1 1

find 0 0

add 1 1

find 0 0

Output

Input

13

add 5 5

add 5 6

add 5 7

add 6 5

add 6 6

add 6 7

add 7 5

add 7 6

add 7 7

find 6 6

remove 7 7

find 6 6

find 4 4

Output

这题我想了很久，有个地方一直错，导致我改了好几天才该对了这题。。这题题意是共有三种操作，添加点，删除点以及查找严格右上方的点。

这里可以先读入所有坐标后去重，然后对于每一个x坐标，维护一个set记录该x坐标下的所有y坐标，便于添加点或者删除点后查找最大的y坐标。然后用线段树维护横坐标上的最大y坐标，便于快速查找。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

#define maxn 200060

int pos[maxn],high[maxn],zhi,ans;

struct node{

	int l,r,h;

}b[4*maxn];

char s[maxn][10];

set<int> myset[maxn];

set<int>::iterator it;

int find(int l,int r,int x)

{

	int mid;

	while(l<=r){

		mid=(l+r)/2;

		if(pos[mid]==x)return mid;

		else if(pos[mid]>x)r=mid-1;

		else l=mid+1;

	}

	if(pos[l]==x)return l;

	else return r;

}

void build(int l,int r,int i)

{

	int mid;

	b[i].l=l;b[i].r=r;b[i].h=0;

	if(l==r)return;

	mid=(l+r)/2;

	build(l,mid,i*2);

	build(mid+1,r,i*2+1);

}

void update(int t1,int i)

{

	int mid;

	if(b[i].l==t1 && b[i].r==t1){

		if(myset[t1].size())

            b[i].h=*(--myset[t1].end());

         else

            b[i].h=-1;

         return;

	}

	mid=(b[i].l+b[i].r)/2;

	if(t1>mid)update(t1,i*2+1);

	else update(t1,i*2);

	b[i].h=max(b[i*2].h,b[i*2+1].h);

}

void question(int l,int r,int h,int i)

{

	int mid;

	if(b[i].h<=h || r>b[i].r || l<b[i].l)return; //这里要注意可能一开始r,l就在区间内

	if(b[i].l==b[i].r){

		if(b[i].h<=h)return;

		ans=b[i].l;return;

	}

	mid=(b[i].l+b[i].r)/2;

	if(r<=mid){

		if(b[i*2].h>h){

			question(l,r,h,i*2);

		}

		else return;

	}

	else if(l>mid){

		if(b[i*2+1].h>h){

			question(l,r,h,i*2+1);

		}

		else return;

	}

	else{

		if(b[i*2].h>h)question(l,mid,h,i*2);

		if(ans!=-1)return;  //这里是关键！如果左子树查不到的话，要查右子树，并不是如果左子树记录的最大高度大于h，就一定能找到，因为左子树还有自身的l限制（即l并不延伸到b[i].l)

		if(b[i*2+1].h>h)question(mid+1,r,h,i*2+1);

		else return;

	}

}

int main()

{

	int n,m,i,j,t,t1,t2,c[maxn],d[maxn];//,ans

	while(scanf("%d",&n)!=EOF)

	{

		t=0;

		for(i=1;i<=n;i++){

			scanf("%s%d%d",s[i],&c[i],&d[i]);

			if(s[i][0]=='a'){

				++t;pos[t]=c[i];

			}

		}

		sort(pos+1,pos+1+t);

		m=1;

		for(i=2;i<=t;i++){

			if(pos[i]!=pos[m]){

				m++;pos[m]=pos[i];

			}

		}

		build(1,m,1);

		memset(high,-1,sizeof(high));

		for(i=1;i<=m;i++){

			myset[i].clear();

		}

		for(i=1;i<=n;i++){

			if(s[i][0]=='a'){

				t1=find(1,m,c[i]);

				myset[t1].insert(d[i]);

				update(t1,1);

			}

			else if(s[i][0]=='r'){

				t1=find(1,m,c[i]);

				myset[t1].erase(d[i]);

				update(t1,1);

			}

			else

             {

                t2=upper_bound(pos+1,pos+1+m,c[i])-pos;

                if(t2>m){

                	printf("-1\n");continue;

                }

                ans=-1;

                question(t2,m,d[i],1);

                if(ans==-1)

                    printf("-1\n");

                else

                    printf("%d %d\n",pos[ans],*myset[ans].upper_bound(d[i]));

             }

		}

	}

	return 0;

}

巴特西

Codeforces Beta Round #19 D. Points

最新文章

热门文章