# [BZOJ 1208][HNOI2004] 宠物收养所【Treap】

• 2018-03-04
• 0
• 0

## Problem:

Time Limit: 10 Sec    Memory Limit: 162 MB

```5
0 2
0 4
1 3
1 2
1 5
```

### Sample Output

```3
(abs(3-2)+abs(2-4)=3，最后一个领养者没有宠物可以领养)
```

## Code: O(nlogn) [2864K, 196MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 80005
#define INFINT 0x3f3f3f3f
#define MOD 1000000
using namespace std;
typedef pair<int, int> PII;

inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int n, tp, v, treap_tp, unpl = 0;

struct Treap{
int root, val[MAXN], wt[MAXN], size[MAXN], lc[MAXN], rc[MAXN], topp;

inline void update(int u) {size[u] = size[lc[u]] + size[rc[u]] + 1;}

inline PII split(int u, int pos){
if(!pos) return make_pair(0, u);
int l = lc[u], r = rc[u];
if(pos == size[l]) return lc[u] = 0, update(u), make_pair(l, u);
else if(pos == size[l] + 1) return rc[u] = 0, update(u), make_pair(u, r);
else if(pos < size[l]){
PII roots = split(l, pos);
return lc[u] = roots.second, update(u), make_pair(roots.first, u);
}
else{
PII roots = split(r, pos - size[l] - 1);
return rc[u] = roots.first, update(u), make_pair(u, roots.second);
}
}

inline int merge(int u, int v){
if(!u || !v) return u | v;
if(wt[u] < wt[v]) return rc[u] = merge(rc[u], v), update(u), u;
else return lc[v] = merge(u, lc[v]), update(v), v;
}

inline int rnk(int x){
int u = root, delta = 0, res = INFINT;
while(u){
if(x == val[u]) res = min(res, delta + size[lc[u]] + 1);
if(x > val[u]) delta += size[lc[u]] + 1, u = rc[u];
else u = lc[u];
}
return res < INFINT ? res : delta;
}

inline int kth(int k){
int u = root;
while(u){
if(k == size[lc[u]] + 1) return val[u];
if(k < size[lc[u]] + 1) u = lc[u];
else k -= size[lc[u]] + 1, u = rc[u];
}
}

inline int pred(int x){
int u = root, res = -INFINT;
while(u){
if(val[u] < x) res = max(res, val[u]), u = rc[u];
else u = lc[u];
}
return res;
}

inline int succ(int x){
int u = root, res = INFINT;
while(u){
if(val[u] > x) res = min(res, val[u]), u = lc[u];
else u = rc[u];
}
return res;
}

inline void insert(int x){
int k = rnk(x); PII roots = split(root, k);
val[++topp] = x, wt[topp] = rand(), size[topp] = 1;
root = merge(merge(roots.first, topp), roots.second);
}

inline void erase(int x){
int k = rnk(x); PII rootr = split(root, k), rootl = split(rootr.first, k - 1);
root = merge(rootl.first, rootr.second);
}
} treap;

int main(){
getint(n);
for(register int i = 1; i <= n; i++){
getint(tp), getint(v);
if(!treap.root) treap_tp = tp, treap.insert(v);
else if(tp == treap_tp) treap.insert(v);
else{
int low = treap.pred(v + 1), up = treap.succ(v - 1);
if(v - low <= up - v) unpl = (unpl + v - low) % MOD, treap.erase(low);
else unpl = (unpl + up - v) % MOD, treap.erase(up);
}
}
printf("%d\n", unpl);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai