首页 > 代码库 > codeforces Beta Round #19 D. Point (线段树 + set)
codeforces Beta Round #19 D. Point (线段树 + set)
题目大意:
对平面上的点进行操作。
add x y 在 (x,y )上加一个点。
remove x y 移除 (x,y)上的点。
find x y 求出在(x,y)右上角离他最近的点,优先级是靠左,靠下。
思路分析:
find 操作 比较麻烦。
要保证x大的同时还要确保x最小,而且该x上还要有点。
这样要找大的时候要小的,就是在线段树上选择性的进入左子树还是右子树。
所以核心就是,用set维护叶子节点。
然后查找的时候去叶子节点找,如果这个叶子节点有蛮子的 x y 就输出,否则回溯去另外一个子树。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <set> #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define maxn 400005 using namespace std; set <int> cq[maxn]; int cnt[maxn<<2]; int mmax[maxn<<2]; struct node { char type[10]; int x,y; } save[maxn]; int x[maxn<<1]; void Insert(int num,int s,int e,int pos,int val,bool flg) { if(s==e) { if(flg) { cnt[num]++; cq[s].insert(val); mmax[num]=max(mmax[num],*(--cq[s].end())); } else { cnt[num]--; cq[s].erase(val); if(!cq[s].empty())mmax[num]=max(mmax[num],*(--cq[s].end())); else mmax[num]=0; } return; } int mid=(s+e)>>1; if(pos<=mid)Insert(lson,pos,val,flg); else Insert(rson,pos,val,flg); cnt[num]=cnt[num<<1]+cnt[num<<1|1]; mmax[num]=max(mmax[num<<1],mmax[num<<1|1]); } int ansx,ansy; bool query(int num,int s,int e,int l,int r,int pos,int val) { int mid=(s+e)>>1; if(l<=s && r>=e) { if(s==e) { set<int>::iterator it = cq[s].upper_bound(val); if(it==cq[s].end()) { return false; } else { ansx=s; ansy=*it; return true; } } else { if(mmax[num<<1]>val) { if(query(lson,l,r,pos,val))return true; } if(mmax[num<<1|1]>val) { if(query(rson,l,r,pos,val))return true; } return false; } } if(r<=mid) { if(query(lson,l,r,pos,val))return true; } else if(l>mid) { if(query(rson,l,r,pos,val))return true; } else { if(query(lson,l,mid,pos,val))return true; if(query(rson,mid+1,r,pos,val))return true; } return false; } int main() { int n; memset(cnt,0,sizeof cnt); memset(mmax,0,sizeof mmax); scanf("%d",&n); int top=1; for(int i=1; i<=n; i++) { scanf("%s%d%d",save[i].type,&save[i].x,&save[i].y); x[top++]=save[i].x; x[top++]=save[i].y; } sort(x+1,x+top); int m = unique(x+1,x+top)-x; for(int i=1; i<=n; i++) { if(save[i].type[0]=='a') { int l=lower_bound(x+1,x+m,save[i].x)-x; Insert(1,1,m,l,save[i].y,1); } else if(save[i].type[0]=='r') { int l=lower_bound(x+1,x+m,save[i].x)-x; Insert(1,1,m,l,save[i].y,0); } else { int l=upper_bound(x+1,x+m,save[i].x)-x; if(query(1,1,m,l,m,l,save[i].y))printf("%d %d\n",x[ansx],ansy); else printf("-1\n"); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。