codeforces 19D Points

思路: 線段樹+單點更新 分析: 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;  
}