BZOJ 1208 （可持久化Treap,合并与分裂操作）

本文主要是介绍BZOJ 1208 （可持久化Treap,合并与分裂操作），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1208: [HNOI2004]宠物收养所

Time Limit: 10 Sec   Memory Limit: 162 MB
Submit: 4965   Solved: 1902
[ Submit][ Status][ Discuss]

Description

Input

Output

Sample Input

Sample Output

/*

Treap的简单应用 不过需要注意几个细节！ 寻找前驱和后继节点的时候，是找的value值为v的严格前驱和非严格后继节点；

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define inf 0x0f0f0f0f
#define mod 1000000
int abs(int x){ return (x>=0?x:-x); }
struct Node {Node *ch[2];int rank,value,siz;Node(){ ch[0] = ch[1] = NULL; }Node(int v,int r) {ch[0] = ch[1] = NULL;value = v; rank = r;siz = 1;}void push_up() {siz = 1;if(ch[0]!=NULL) siz += ch[0]->siz;if(ch[1]!=NULL) siz += ch[1]->siz;}
}*root;
int res,tag;
typedef pair<Node *,Node *> DNode;
Node *merge(Node *(&node1),Node *(&node2)) {if(node1==NULL) return node2;if(node2==NULL) return node1;if(node1->rank > node2->rank){node1->ch[1] = merge(node1->ch[1],node2);node1->push_up();return node1;}else{node2->ch[0] = merge(node1,node2->ch[0]);node2->push_up();return node2;}
}
DNode split(Node *(&node),int k) {if(node==NULL) return DNode(NULL,NULL);if(k<=0)         return DNode(NULL,node);if(node->siz<=k) return DNode(node,NULL);DNode ans = DNode(NULL,NULL);if(node->ch[0]!=NULL&&node->ch[0]->siz >= k) {ans = split(node->ch[0],k);node->ch[0] = ans.second;node->push_up();ans.second = node;}else {int size = (node->ch[0]!=NULL?node->ch[0]->siz+1:1);ans = split(node->ch[1],k-size);node->ch[1] = ans.first;node->push_up();ans.first = node;}return ans;
}
//找node的严格前驱节点
Node *getPre(Node *(&node),int v) {if(node == NULL) return NULL;Node *ans = node;if(node->value >= v) ans = getPre(node->ch[0],v);else {ans = getPre(node->ch[1],v);if(ans==NULL) ans = node;}return ans;
}
//找node的非严格后继节点
Node *getNext(Node *(&node),int v) {if(node == NULL) return NULL;Node *ans = node;if(node->value >= v){ans = getNext(node->ch[0],v);if(ans==NULL) ans = node;}else ans = getNext(node->ch[1],v);return ans;
}
//查找严格<v节点个数
int search(Node *(&node),int v) {if(node == NULL) return 0;if(node->value >= v) return search(node->ch[0],v);else {int k = 1;if(node->ch[0]!=NULL) k += node->ch[0]->siz;return k + search(node->ch[1],v);}
}
void insert(int v) {int k = search(root,v);DNode tem = split(root,k);Node *node = new Node(v,rand());tem.first = merge(tem.first,node);root = merge(tem.first,tem.second);
}
void earse(int v){Node *left = getPre(root,v);Node *right = getNext(root,v);int k = search(root,v),ldis = inf,rdis = inf;if(left!=NULL)  ldis = v - left->value;if(right!=NULL) rdis = right->value - v;//printf("%d,%d\n",ldis,rdis);if(ldis<=rdis){res = (res + ldis%mod)%mod;DNode tem1 = split(root,k-1);DNode tem2 = split(tem1.second,1);delete tem2.first; tem2.first = NULL;root = merge(tem1.first,tem2.second);}else {res = (res + rdis%mod)%mod;DNode tem1 = split(root,k);DNode tem2 = split(tem1.second,1);delete tem2.first; tem2.first = NULL;root = merge(tem1.first,tem2.second);}
}
void solve(int flag,int v){if(root==NULL) tag = flag;if(flag==tag) insert(v);else          earse(v);
}
void delet(Node *(node)){if(node==NULL) return;delet(node->ch[0]);if(node->ch[0]!=NULL){delete node->ch[0];node->ch[0]=NULL;}delet(node->ch[1]);if(node->ch[1]!=NULL){delete node->ch[1];node->ch[1]=NULL;}delete node; node = NULL;
}
void init(){res = tag = 0;delet(root);root = NULL;
}
int main() {int n,flag,v;//freopen("Test.txt","r",stdin);while(~scanf("%d",&n)){init();for(int i = 1;i<=n;i++){scanf("%d%d",&flag,&v);solve(flag,v);}printf("%d\n",res);}return 0;
}

这篇关于BZOJ 1208 （可持久化Treap,合并与分裂操作）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---