CF 19D 线段树+set压缩坐标轴+离散化map

题意:

n个操作,在200000*200000的平面上加删点

find 严格在坐标右上角,x最小,再y最小的点

线段树做,区间为离散化后的 X轴坐标 ,维护区间点数 和 最小的 y 值 ( 维护最小y值是重要优化 )

#include <stdio.h>
#include <string.h>
#include <queue>
#include <set>
#include <functional>
#include <map> #define N 201000
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define Mid(x,y) ((x+y)>>1)
#define ll int
using namespace std;
inline ll Max(ll a, ll b){ return a>b?a:b;}
inline ll Min(ll a, ll b){ return a<b?a:b;} int Point[N];
map<int, int> mymap; vector<int>G; struct node{
int l,r;
int num;
int maxy;
}tree[N*4];
set<int> treeset[N];
set<int> ::iterator p; void build( int l, int r, int id){
tree[id].l = l, tree[id].r = r;
tree[id].num = 0;
tree[id].maxy = 0;
if(l==r)return ;
int mid = Mid(l, r);
build(l, mid, L(id));
build(mid+1, r, R(id));
} void insert(int pos, int id, int data, bool add){// add = true 插入data =false 删除data
if(tree[id].l == tree[id].r){
if(add)
treeset[pos].insert(data); else
treeset[pos].erase(data);
tree[id].num = treeset[pos].size();
if(tree[id].num)
tree[id].maxy = *treeset[pos].rbegin();
else
tree[id].maxy = 0;
return ;
}
int mid = Mid(tree[id].l, tree[id].r); if(pos <= mid)insert(pos, L(id), data, add);
else insert(pos, R(id), data, add); tree[id].num = tree[L(id)].num + tree[R(id)].num;
tree[id].maxy =Max( tree[L(id)].maxy , tree[R(id)].maxy);
} int query(int l, int r, int y, int id){
if( tree[id].l == tree[id].r ){
if(tree[id].num){ p = treeset[ tree[id].l ].upper_bound(y);
if(p != treeset[ tree[id].l ].end() ){
printf("%d ", Point[ tree[id].l ]);
return *p;
}
}
return -1;
}
if( l == tree[id].l && tree[id].r == r){
if(tree[id].num == 0 || tree[id].maxy <= y)
return -1;
}
int mid = Mid(tree[id].l , tree[id].r);
if(r <= mid) return query(l, r, y, L(id));
if(mid < l) return query(l, r, y, R(id)); int treey =query(l, mid, y, L(id));
if(treey > y) return treey;
return query(mid+1, r, y, R(id));
} struct QUE{
char c;
int u,v;
}que[N];
set<int> tempset;
void Input(int n){
int u,v; char s[10];
tempset.clear();
mymap.clear();
for(int i = 1; i <= n; i++){
scanf("%s %d %d", s, &u, &v);
que[i].c = s[0], que[i].u = u, que[i].v = v;
tempset.insert(u);
}
p = tempset.begin();
int size = tempset.size();
for(int i = 1; i <= size ; i++,p++){
mymap.insert(pair<int, int>(*p, i));
Point[i] = *p;
}
}
int go(int x){
return mymap.find(x) -> second;
}
int main(){
int n;
char s[10];
while(~scanf("%d",&n)){
for(int i = 1; i<=200001; i++)treeset[i].clear();
build(1,200001,1); Input(n); for(int i = 1; i<=n; i++){
int u = que[i].u, v = que[i].v;
if(que[i].c == 'a')
insert(go(u),1,v,1); else if(que[i].c == 'r')
insert(go(u),1,v,0); else if(que[i].c == 'f')
printf("%d\n", query(go(u)+1, 200001, v, 1)); }
}
return 0;
}
/*
7
add 1 1
add 3 4
find 0 0
remove 1 1
find 0 0
add 1 1
find 0 0 ans:
1 1
3 4
1 1 13
add 5 5
add 5 6
add 5 7
add 6 5
add 6 6
add 6 7
add 7 5
add 7 6
add 7 7
find 6 6
remove 7 7
find 6 6
find 4 4 ans:
7 7
-1
5 5 10
add 5 7
add 2 1
add 8 8
add 5 10
add 2 5
find 7 5
find 8 3
find 2 2
find 5 4
find 2 6 ans:
8 8
-1
5 7
8 8
5 7 */
上一篇:Dynamic Flash Messages


下一篇:dubbo升级spring4与cxf