题解CF19D Points

· · 题解

Problem

题目已经说的很清楚了，只不过还有要注意的就是这个“右上方”指的是严格大于，也就是 x_1>x_2，y_1>y_2 。

Solution

首先看到值域的数据范围我们可以想到先离散化一下。

然后我们考虑用线段树维护横坐标为 1,2,3,4... 时的纵坐标最大值。（也就是每一个横坐标上的最大纵坐标，在这个基础上线段树维护最大值。）

对于每一个横坐标可以开一个 set 维护这个坐标内部的点。

那么题目上的操作就很好实现了，添加操作就是先看看可不可以取代当前的那个位置上的最大值，然后再插入进 set 里。

删除操作就是先在对应横坐标的 set 里删除，然后再用当前 set 里的最大值放进线段树里，覆盖掉原来的那个。

最后 查找操作就是先在线段树上二分，找到最左边的，且横坐标大于 x ，值大于 y 的位置。

（注意这里的值指的是线段树维护的那个 Max ，因为我们这里只是看在这个坐标上有没有解，至于题目要求的还要 y 尽可能小，我们一会先定位横坐标，再在这个横坐标的 set 上找。）

于是我们再在这个位置上的 set 当中二分找到第一个大于 y 的值，再映射回原数组（因为离散化了的），就是答案了。

Code

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
    x=0;char ch=getchar();bool f=false;
    while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}
template <typename T>
inline void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
    return ;
}
const int N=4e5+5; 
#define ll long long
struct Query{int op,x,y;}Q[N];
int n,m,b[N],cnt,Max[N<<2];
set<int> ST[N];
void Pushup(int x){Max[x]=max(Max[x<<1],Max[x<<1|1]);return ;}
void Modify(int x,int l,int r,int pos,int v){
    if(l==r){Max[x]=max(Max[x],v);return ;}
    int mid=l+r>>1;
    if(pos<=mid) Modify(x<<1,l,mid,pos,v);
    else Modify(x<<1|1,mid+1,r,pos,v);
    Pushup(x);
    return ;
} 
void Change(int x,int l,int r,int pos,int v){
    if(l==r){Max[x]=v;return ;}
    int mid=l+r>>1;
    if(pos<=mid) Change(x<<1,l,mid,pos,v);
    else Change(x<<1|1,mid+1,r,pos,v);
    Pushup(x);
    return ;
} 
int QueryPos(int x,int l,int r,int X,int Y){
    if(l==r){
        if(Max[x]>Y) return l;
        return -1;
    }
    int mid=l+r>>1,res=-1;
    if(X<=mid&&Max[x<<1]>Y) res=QueryPos(x<<1,l,mid,X,Y);
    if(~res) return res;
    if(Max[x<<1|1]>Y) return QueryPos(x<<1|1,mid+1,r,X,Y); 
    return -1;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        char op[10];int x,y;
        scanf("%s",op);read(x),read(y);
        if(op[0]=='a') Q[i].op=1,Q[i].x=x,Q[i].y=y; 
        else if(op[0]=='r') Q[i].op=2,Q[i].x=x,Q[i].y=y; 
        else Q[i].op=3,Q[i].x=x,Q[i].y=y; 
        b[++cnt]=x,b[++cnt]=y;
    }
    sort(b+1,b+cnt+1);
    int idx=unique(b+1,b+cnt+1)-b-1;
    for(int i=1;i<=n;i++) Q[i].x=lower_bound(b+1,b+idx+1,Q[i].x)-b,Q[i].y=lower_bound(b+1,b+idx+1,Q[i].y)-b;
    for(int i=1;i<=n;i++){
        if(Q[i].op==1) ST[Q[i].x].insert(Q[i].y),Modify(1,1,idx,Q[i].x,Q[i].y);
        else if(Q[i].op==2){
            ST[Q[i].x].erase(ST[Q[i].x].find(Q[i].y));
            if(ST[Q[i].x].empty()){
                Change(1,1,idx,Q[i].x,0);
                continue;
            }
            Change(1,1,idx,Q[i].x,*ST[Q[i].x].rbegin());
        }
        else{
            int Pos=QueryPos(1,1,idx,Q[i].x+1,Q[i].y);
            if(Pos==-1) puts("-1");
            else write(b[Pos]),putchar(' '),write(b[*ST[Pos].upper_bound(Q[i].y)]),putchar('\n');
        }
    }
    return 0;
}