codeforces 19D Points

点击打开cf 19D

思路: 线段树+单点更新

分析:

1 题目的意思是给定一些点和n个操作，这些点都是在原点(0 , 0)的右边，现在给定三种操作

add x y 是把(x , y)这个点加入

remove x y 是把(x , y)这个点删除

find x y是查找(x , y)点的右边的点满足x' > x && y' > y 并且有x'和y‘尽量的小

2 题目给定的数据是n是2*10^5，但是点的最大值为10^9，所以我们应该要进行点的离散化。但是我们只要对x进行离散化即可

3 我们利用set来保存每一个x对应的y的集合，然后我们利用线段树来维护一个x区间的最大的y。

为什么要用线段树呢？因为我们知道我们只要只要当前区间的最大值就能够判断是否有没有存在这样的点，然后我们利用二分逼近的思想去求出这个x。只要我们求出了x，那么我们就可以利用之前的set来找比y大的y'，这一步可以利用set的内置的lower_bound

4 有一点很重要的就是，由于set和map的存储结构不是线性的，因此它们内置了lower_bound和upper_bound，所以我们利用内置，如果使用通用的时间效率及其底下

代码:

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-09-08                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ************************************************/
#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define Lson(x) (x<<1)
#define Rson(x) (Lson(x)|1)
#define Mid(x,y) ((x+y)>>1)
#define Sum(x,y) (x+y)

const int MAXN = 200010;

struct Edge{
    int mark;
    int x;
    int y;
};
Edge e[MAXN];

struct Node{
    int left;
    int right;
    int max_y;
};
Node node[4*MAXN];

int n , m;
int num[MAXN];
set<int>s[MAXN];

void input(){
    m = 1;
    char str[10];
    for(int i = 1 ; i <= n ; i++){
        scanf("%s%d%d" , str , &e[i].x , &e[i].y);
        if(str[0] == 'a')
            e[i].mark = 1;
        else if(str[0] == 'r')
            e[i].mark = 2;
        else
            e[i].mark = 3;
        s[m].clear();
        num[m++] = e[i].x;
    }
}

inline void push_up(int pos){
    node[pos].max_y = max(node[Lson(pos)].max_y , node[Rson(pos)].max_y);
}

void buildTree(int left , int right , int pos){
    node[pos].left = left;
    node[pos].right = right;
    node[pos].max_y = -1;
    if(left == right)
        return;
    int mid = Mid(left , right);
    buildTree(left , mid , Lson(pos));
    buildTree(mid+1 , right , Rson(pos));
}

void update(int x , int pos){
    if(node[pos].left == node[pos].right){
        if(s[x].size())
            node[pos].max_y = *(--s[x].end());
        else
            node[pos].max_y = -1;
        return;
    }
    int mid = Mid(node[pos].left , node[pos].right); 
    if(x <= mid)
        update(x , Lson(pos));
    else
        update(x , Rson(pos));
    push_up(pos);
}

int query(int x , int y , int pos){
    if(node[pos].right <= x)    
        return -1;
    if(node[pos].max_y <= y)
        return -1;
    if(node[pos].left == node[pos].right)
        return node[pos].left;
    int t = query(x , y , Lson(pos)); 
    if(t == -1)
        t = query(x , y , Rson(pos));
    return t;
}

void solve(){
    sort(num+1 , num+1+m); 
    m = unique(num+1 , num+1+m)-(num+1);
    buildTree(1 , m , 1);

    for(int i = 1 ; i <= n ; i++){
        int x = upper_bound(num+1 , num+1+m , e[i].x)-(num+1);
        int y = e[i].y;
        // add
        if(e[i].mark == 1){
            s[x].insert(y);
            update(x , 1);
        }
        // remove
        else if(e[i].mark == 2){
            s[x].erase(y);
            update(x , 1);
        }
        // find
        else{
            int ans = query(x , y , 1);
            if(ans == -1)
                puts("-1");
            else{
                printf("%d %d\n" , num[ans] , *s[ans].upper_bound(y));
            }
        } 
    }
}

int main(){
    while(scanf("%d%*c" , &n) != EOF){
        input();
        solve();
    }
    return 0;
}