预览加载中，请您耐心等待几秒...

ACM模板.pdf

预览
1/10
2/10
3/10
4/10
5/10
6/10
7/10
8/10
9/10
10/10

亲，该文档总共199页，到这已经超出免费预览范围，如果喜欢就直接下载吧～

下载提示 文本预览

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

第一章数据结构1、splaystructnode{intsize;node*c[2],*p;};nodea[N],*root,*nullNode;intcnt;voidpushUp(node*p){if(p==nullNode)return;p->size=1+p->c[0]->size+p->c[1]->size;}voidpushDown(node*p){if(p==nullNode)return;}node*newNode(intval,node*p){node*e=&a[cnt++];e->c[0]=e->c[1]=nullNode;e->p=p;e->size=1;returne;}voidinit(){nullNode=0;nullNode=newNode(0,nullNode);nullNode->size=0;root=newNode(0,nullNode);root->c[1]=newNode(0,root);pushUp(root);}voidzig(node*x){node*p=x->p,*q=p->p;p->c[0]=x->c[1];1if(x->c[1]!=nullNode)x->c[1]->p=p;x->c[1]=p;p->p=x;x->p=q;if(q!=nullNode){if(q->c[0]==p)q->c[0]=x;elseq->c[1]=x;}pushUp(p);pushUp(x);if(root==p)root=x;}voidzag(node*x){node*p=x->p,*q=p->p;p->c[1]=x->c[0];if(x->c[0]!=nullNode)x->c[0]->p=p;x->c[0]=p;p->p=x;x->p=q;if(q!=nullNode){if(q->c[0]==p)q->c[0]=x;elseq->c[1]=x;}pushUp(p);pushUp(x);if(root==p)root=x;}voidsplay(node*x,node*goal){while(x->p!=goal){if(x->p->p!=goal){pushDown(x->p->p);pushDown(x->p);pushDown(x);if(x->p->p->c[0]==x->p)2{if(x->p->c[0]==x)zig(x->p),zig(x);elsezag(x),zig(x);}else{if(x->p->c[1]==x)zag(x->p),zag(x);elsezig(x),zag(x);}}else{pushDown(x->p);pushDown(x);if(x->p->c[0]==x)zig(x);elsezag(x);}}}voidselect(intk,node*goal){node*p=root;pushDown(p);while(k!=p->c[0]->size+1){if(k<=p->c[0]->size)p=p->c[0];else{k-=1+p->c[0]->size;p=p->c[1];}pushDown(p);}splay(p,goal);}node*build(intL,intR,charstr[],node*p){if(L>R)returnnullNode;intmid=(L+R)>>1;node*e=newNode(str[mid]=='('?1:-1,p);e->c[0]=build(L,mid-1,str,e);3e->c[1]=build(mid+1,R,str,e);pushUp(e);returne;}2、TreapstructNode{intval,size,pri;intL,R;};Nodea[N];inte;intnewNode(intval){intx=++e;a[x].val=val;a[x].size=1;a[x].L=a[x].R=-1;a[x].pri=rand();returnx;}voidpushUp(intk){if(k==-1)return;a[k].size=1;if(a[k].L!=-1)a[k].size+=a[a[k].L].size;if(a[k].R!=-1)a[k].size+=a[a[k].R].size;}voidrotL(int&x){inty=a[x].R;a[x].R=a[y].L;a[y].L=x;pushUp(x);pushUp(y);4x=y;}voidrotR(int&x){inty=a[x].L;a[x].L=a[y].R;a[y].R=x;pushUp(x);pushUp(y);x=y;}voidinsert(int&k,intval){if(k==-1){k=newNode(val