BZOJ3685 普通 van Emde Boas 树 题解（vEB 树模板题）

（题目描述略）

vEB 树的模板题，似乎用 zkw 线段树也可以过。

因为 vEB 树的建树过程花费大量时间，所以若用 STL 中的 vector 开不定长数组，其常数之大难免有超时的危险。解决方法是用统一的外部数组保存，记下每个节点在外部数组中的开始位置，并保证每个节点在外部数组中占用的地址连续。

最后，还是请 KikiDMW 大神帮助了面对超时问题无解的笔者，写了一段读入优化的代码，才勉强保证了时间在可接受的范围之内。

这里有个细节：vEB 树维护的是从 0 到 n - 1 的区间，所以建树时大小为 n + 1。

代码如下：

#include"math.h" #include"stdio.h" #define MAX_N (1500000) #define NIL (-1) #define Exchange_Integer(x,y) \ { \ int __tmp_x=x; \ x=y,y=__tmp_x; \ } struct VANEMDEBOAS_TREE; inline void in(int &x); int cluster_top=0; VANEMDEBOAS_TREE *cluster[MAX_N]; struct VANEMDEBOAS_TREE { int c,max,min,sqr,u; VANEMDEBOAS_TREE *summary; int High(int x) { return (int)(x/sqr); } int Low(int x) { return x%sqr; } int Index(int x,int y) { return x*sqr+y; } inline int Maximum() { return max; } inline int Minimum() { return min; } bool Member(int x) { if(min==x||max==x) return true; if(u<=2) return false; return cluster[c+High(x)]->Member(Low(x)); } int Successor(int x) { if(u<=2) if(max==1&&x==0) return 1; else return NIL; if(min!=NIL&&min>x) return min; int max_low=cluster[c+High(x)]->Maximum(); if(max_low!=NIL&&max_low>Low(x)) return Index(High(x),cluster[c+High(x)]->Successor(Low(x))); int succ_cluster=summary->Successor(High(x)); if(succ_cluster==NIL) return NIL; return Index(succ_cluster,cluster[c+succ_cluster]->Minimum()); } int PRedecessor(int x) { if(u<=2) if(min==0&&x==1) return 0; else return NIL; if(max!=NIL&&max<x) return max; int min_low=cluster[c+High(x)]->Minimum(); if(min_low!=NIL&&min_low<Low(x)) return Index(High(x),cluster[c+High(x)]->Predecessor(Low(x))); int pred_cluster=summary->Predecessor(High(x)); if(pred_cluster==NIL) if(min!=NIL&&min<x) return min; else return NIL; return Index(pred_cluster,cluster[c+pred_cluster]->Maximum()); } void Insert(int x) { if(min!=NIL&&min!=x) { if(min>x) Exchange_Integer(min,x); if(u>2) { if(cluster[c+High(x)]->Minimum()==NIL) summary->Insert(High(x)); cluster[c+High(x)]->Insert(Low(x)); } if(max<x) max=x; } else if(min!=x) max=min=x; } void Delete(int x) { if(max!=min&&u>2) { if(min==x) min=x=Index(summary->Minimum(),cluster[c+summary->Minimum()]->Minimum()); cluster[c+High(x)]->Delete(Low(x)); if(cluster[c+High(x)]->Minimum()==NIL) { summary->Delete(High(x)); if(max==x) if(summary->Maximum()!=NIL) max=Index(summary->Maximum(),cluster[c+summary->Maximum()]->Maximum()); else max=min; } else if(max==x) max=Index(High(x),cluster[c+High(x)]->Maximum()); } else if(max!=min&&u==2) max=min=1-x; else if(min==x) max=min=NIL; } }; void VEBT_Create(VANEMDEBOAS_TREE *V,int u) { V->max=V->min=NIL; V->u=u; if(u>2) { V->c=cluster_top; V->sqr=(int)sqrt(u); V->sqr=V->sqr*V->sqr<u?V->sqr+1:V->sqr; int x=u/V->sqr; for(int i=0;i<x;i++) cluster[cluster_top++]=new VANEMDEBOAS_TREE; if(u%V->sqr>0) cluster[cluster_top++]=new VANEMDEBOAS_TREE; for(int i=0;i<x;i++) VEBT_Create(cluster[V->c+i],V->sqr); if(u%V->sqr>0) VEBT_Create(cluster[V->c+x++],u%V->sqr); V->summary=new VANEMDEBOAS_TREE; VEBT_Create(V->summary,x); } else V->summary=NULL; } int main() { int m,n; VANEMDEBOAS_TREE *vEBTree=new VANEMDEBOAS_TREE; in(n);in(m); VEBT_Create(vEBTree,n+1); while(m--) { in(n); switch(n) { case 1:in(n);vEBTree->Insert(n);break; case 2:in(n);vEBTree->Delete(n);break; case 3:printf("%d\n",vEBTree->Minimum());break; case 4:printf("%d\n",vEBTree->Maximum());break; case 5:in(n);printf("%d\n",vEBTree->Predecessor(n));break; case 6:in(n);printf("%d\n",vEBTree->Successor(n));break; case 7:in(n);printf("%d\n",vEBTree->Member(n)?1:-1);break; } } return 0; } inline void in(int &x){ x = 0; char c; c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9'){ x = x * 10 + c - '0'; c = getchar(); } }