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·105, 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·105) — 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 109.
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.
Examples
Input
7
add 1 1
add 3 4
find 0 0
remove 1 1
find 0 0
add 1 1
find 0 0
Output
1 1
3 4
1 1
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
7 7
-1
5 5
题意翻译
在一个笛卡尔坐标系中,定义三种操作:
1.add x y :在坐标系上标记一个点(x,y),保证(x,y)在添加前不在坐标系上.
2.remove x y :移除点(x,y),保证(x,y)在移除前已在坐标系上.
3.find x y :找到所有已标记并在(x,y)右上方的点中,最左边的点,若点不唯一,选择最下面的一个点; 如果没有符合要求的点,给出"-1",否则给出x y.
现有n( n<=2*10^5 )个操作,对于每个find操作,输出结果.
这道题看到“三种操作”就能看出这是一道“小清新”数据结构题
看到这种找右上方的点的问题,某些大佬(gjm,xyc,lpl)直接蹦出:
平衡树
此题平衡树可做,鉴定完毕——gjm
像我这种不会平衡树的蒟蒻怎么办,那么我们就要使用我们的Sometimes_ Tle _ Library大法中的set了
那么我们的思路就基本上确定了,开一个set(结构体类型存一个点),然后优先按x轴排序,再按y轴排序,每次找就upper _ bound一下
水题,我三分钟切了——xyc
但是,毕竟是Sometimes_ Tle _ Library,这道题上果然会T…
那我们可以怎么办呢?
光用set肯定不行,但是对于这种插入删除而且肯定要排序的情况好像必须要用set
所以我们可以考虑给每一个x坐标都开一个set
那么我们只需要每次find操作的时候,先确定x的位置,然后在那个x对应的set里面用自带的upper _ bound函数确定y就可以了
那么怎么确定x呢?
线段树!
我们可以用线段树维护区间最大值,每次加入点或者删除点的时候就单点修改一下,查询x就要找
在qxi右边的最靠左的max大于qyi的那个x
所以思路就有了
- 离线,离散化
- 建树,set
- 对于每次询问,先区间查询找到x,然后upper_bound找到y
几个细节
这道题还是有细节的
1.set的用法
这道题要在几个地方用到set
每次插入删除的时候,更新线段树的时候(访问最大值),最后找y
插入删除很简单,用insert和erase就可以
s[q[i].x].insert(q[i].y);
s[q[i].x].erase(s[q[i].x].find(q[i].y));
访问最大值,这里需要用到一个神奇的东西
seg[u].val=*(--s[x].end());
而不能写成
seg[u].val=*(s[x].end()-1);
找y直接upper_bound,注意只需要一个参数y,不需要头尾
*s[pos].upper_bound(q[i].y)
2.区间范围最大值查法
这个其实不难,主要是用两个参数去定最大值的区间,具体看代码吧
3.long long问题
这题int就可以(真仁慈)
代码:
# include <cstdio>
# include <algorithm>
# include <cstring>
# include <cmath>
# include <climits>
# include <iostream>
# include <string>
# include <queue>
# include <stack>
# include <vector>
# include <set>
# include <map>
# include <cstdlib>
# include <ctime>
using namespace std;
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=2e5+5;
const int inf=0x7fffffff;
const double eps=1e-7;
template <typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n,sz;
int b[N];
struct qrys{
char s[5];
int x,y;
}q[N];
struct segment_tree{
int l,r,val;
}seg[N<<2];
set<int> s[N];
# define lc (u<<1)
# define rc (u<<1|1)
void build(int u,int l,int r){
seg[u].l=l,seg[u].r=r;
seg[u].val=-1;
if(l==r)return;
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void update(int u,int x){
if(seg[u].l==seg[u].r){
if(s[x].empty())seg[u].val=-1;
else seg[u].val=*(--s[x].end());
return;
}
int mid=seg[u].l+seg[u].r>>1;
if(x<=mid)update(lc,x);
else update(rc,x);
seg[u].val=max(seg[lc].val,seg[rc].val);
}
int query(int u,int l,int r,int k){
if(l>r)return -1;
if(seg[u].val<=k)return -1;
if(seg[u].l==seg[u].r)return seg[u].l;
int mid=seg[u].l+seg[u].r>>1;
if(r<=mid)return query(lc,l,r,k);
else if(l>mid)return query(rc,l,r,k);
else{
int t=query(lc,l,mid,k);
if(t>=0)return t;
else return query(rc,mid+1,r,k);
}
}
int main()
{
read(n);
Rep(i,1,n){
scanf("%s",q[i].s);
read(q[i].x);
read(q[i].y);
b[i]=q[i].x;
}
sort(b+1,b+n+1);
sz=unique(b+1,b+n+1)-b-1;
Rep(i,1,n)q[i].x=lower_bound(b+1,b+sz+1,q[i].x)-b;
build(1,1,sz);
Rep(i,1,n){
if(q[i].s[0]=='a'){
s[q[i].x].insert(q[i].y);
update(1,q[i].x);
}
if(q[i].s[0]=='r'){
s[q[i].x].erase(s[q[i].x].find(q[i].y));
update(1,q[i].x);
}
if(q[i].s[0]=='f'){
int pos=query(1,q[i].x+1,sz,q[i].y);
if(pos==-1)puts("-1");
else printf("%d %d\n",b[pos],*s[pos].upper_bound(q[i].y));
}
}
return 0;
}
没了,祝大家新年快乐 ——lpl