codeforces 19 D. Points（线段树+set二分）

题目链接：http://codeforces.com/contest/19/problem/D

题意：给出3种操作：1）添加点（x，y），2）删除点（x，y），3）查询离（x，y）最近的右上方的点。

且满足添加的点不重复，删除的点一定存在。

题解：只要以x建树，记录下每个结点最大的y值。每次都更新一下。用线段树查找满足条件的最小的x，然后用一个set[x]来存x点下的y点。

然后用二分查找满足条件的最小的y。

#include <iostream>

#include <cstring>

#include <set>

#include <algorithm>

using namespace std;

const int M = 2e5 + 10;

struct T_T {

    char cp[10];

    int x , y;

}num[M];

struct TnT {

    int l , r , max_y;

}T[M << 2];

set<int>se[M];

set<int>::iterator it;

int a[M] , b[M] , c[M] , d[M];

void build(int l , int r , int p) {

    int mid = (l + r) >> 1;

    T[p].l = l , T[p].r = r , T[p].max_y = -1;

    if(T[p].l == T[p].r) {

        return;

    }

    build(l , mid , p << 1);

    build(mid + 1 , r , (p << 1) | 1);

    T[p].max_y = max(T[p << 1].max_y , T[(p << 1) | 1].max_y);

}

void updata(int p , int pos) {

    int mid = (T[p].l + T[p].r) >> 1;

    if(T[p].l == T[p].r && T[p].l == pos) {

        if(se[T[p].l].size()) {

            it = (--se[T[p].l].end());

            T[p].max_y = *it;

        }

        else {

            T[p].max_y = -1;

        }

        return ;

    }

    if(mid >= pos) {

        updata(p << 1 , pos);

    }

    else {

        updata((p << 1) | 1 , pos);

    }

    T[p].max_y = max(T[p << 1].max_y , T[(p << 1) | 1].max_y);

}

int query(int p , int x , int y) {

    if(T[p].r <= x) {

        return -1;

    }

    if(T[p].max_y <= y) {

        return -1;

    }

    if(T[p].l == T[p].r) {

        return T[p].r;

    }

    int t = query(p << 1 , x , y);

    if(t == -1)

        return query((p << 1) | 1 , x , y);

    return t;

}

int main() {

    int n;

    scanf("%d" , &n);

    int count = 0;

    for(int i = 0 ; i < n ; i++) {

        scanf("%s %d %d" , num[i].cp , &num[i].x , &num[i].y);

        if(num[i].cp[0] == 'a') {

            a[count++] = num[i].x;

        }

    }

    sort(a , a + count);

    int cnt = 0;

    a[count] = -1;

    for(int i = 0 ; i < count ; i++) {

        if(a[i] != a[i + 1]) {

            b[cnt++] = a[i];

        }

    }

    build(1 , M , 1);

    for(int i = 0 ; i < n ; i++) {

        if(num[i].cp[0] == 'a') {

            int pos = upper_bound(b , b + cnt , num[i].x) - b;

            se[pos].insert(num[i].y);

            updata(1 , pos);

        }

        if(num[i].cp[0] == 'r') {

            int pos = upper_bound(b , b + cnt , num[i].x) - b;

            se[pos].erase(num[i].y);

            updata(1 , pos);

        }

        if(num[i].cp[0] == 'f') {

            int pos = upper_bound(b , b + cnt , num[i].x) - b;

            int poss = query(1 , pos , num[i].y);

            if(poss != -1) {

                printf("%d %d\n" , b[poss - 1] , *se[poss].upper_bound(num[i].y));

            }

            else {

                printf("-1\n");

            }

        }

    }

    return 0;

}

巴特西

codeforces 19 D. Points（线段树+set二分）

最新文章

热门文章