其实挺好写的。。。(大雾)
理性愉悦大法好。。。
#include<cstdio>
#include<algorithm>
namespace utils{
template<class T>inline void swp(T&a,T&b){
T c=a; a=b, b=c;
}
}using namespace utils;
namespace mempool{
template<class D,int n=100010>struct pool{
D p[n],*k,*s[n],**st;
pool(){
k=p; st=s;
}
inline D*operator()(){
if(st!=s) return *(--st);
return k++;
}
inline void operator[](D*p){
*(st++)=p;
}
};
}
#define tcd template<class D>
#define pnd PN<D>
namespace PHeap{
tcd struct PN{
PN<D>*ch,*pr,*nx;
D data;
};
tcd inline pnd*merge(pnd*a,pnd*b){
if(!b) return a;
if(!a) return b;
if(b->data < a->data) swp(a,b);
b->nx=a->ch; if(a->ch) a->ch->pr=b;
a->ch=b; b->pr=a;
return a;
}
tcd inline pnd*cut(pnd*b){
if(!b)return 0;
if(b->pr){
if(b->pr->ch==b) b->pr->ch=b->nx;
else b->pr->nx=b->nx;
}
if(b->nx)b->nx->pr=b->pr;
b->pr=0,b->nx=0;
return b;
}
tcd inline pnd*decKey(pnd*Root,pnd*node,int amount){
if(Root==node) return Root->data-=amount,Root;
node->data-=amount;
node=cut(node);
return merge(Root,node);
}
tcd inline pnd*Merge_pairing(pnd*fake_root){
static pnd*Arr[100010],**kh;
if(!fake_root) return 0;
int len=0;
kh=Arr;
while(fake_root){
++len;
*kh=fake_root;
fake_root=fake_root->nx;
(*kh)->pr=0; (*kh)->nx=0;
++kh;
}
for(int i=0,_=len&(-2);i<_;i+=2){
Arr[i]=merge(Arr[i],Arr[i+1]);
}
if(len&1) fake_root=Arr[len^1]; else fake_root=0;
for(int i=(len-2)&(-2);i>=0;i-=2){
fake_root=merge(fake_root,Arr[i]);
}
return fake_root;
}
tcd inline pnd*pop(pnd*&heap){
pnd*r=heap;
heap=heap->ch;
if(heap) heap->pr=0;
r->ch=0;
heap=Merge_pairing(heap);
return r;
}
tcd inline pnd*show(pnd*k){//whatever you want...
//the fact is I had written this but I deleted by mistake...
}
} using namespace PHeap;
namespace debug_suit{
struct Packaged_int{
int a,id;
inline Packaged_int&operator-=(int b){
return a-=b,*this;
}
inline void print(){
printf("#%d[%d]",id,a);
}
inline bool operator<(Packaged_int b){
return a<b.a;
}
};
}using namespace debug_suit;
typedef PN<Packaged_int> PI;
mempool::pool<PI> All;
PI*nodes[100010];
int main(){
int now=0,d,p,r;
PI*n,*R;
char operate[30];
for(int i=0;i<20;++i){
nodes[now]=All();
nodes[now]->data=(Packaged_int){i,now};
++now;
}
for(int i=1;i<20;++i){
merge(nodes[0],nodes[i]);
}
while(~scanf("%s",operate)){
switch(operate[0]){
case 'S':
//show
scanf("%d",&d);
show(nodes[d]);
break;
case 'N':
//new
nodes[now]=All();
scanf("%d",&d);
nodes[now]->data=(Packaged_int){d,now};
++now;
break;
case 'I':
//is root
scanf("%d",&d);
printf("%s\n",nodes[d]->pr?"No":"Yes");
break;
case 'M':
scanf("%d%d",&d,&p);
if(nodes[d]->pr || nodes[p]->pr){
printf("Not roots, break.\n");
break;
}
R=merge(nodes[d],nodes[p]);
R->data.print();
break;
case 'R':
scanf("%d%d%d",&d,&p,&r);
if(p<0){
printf("p>0\n");
break;
}
if(nodes[r]->pr){
printf("Not root, break.\n");
break;
}
///no real root checking is performed; A disjoint set is required to do so...
decKey(nodes[r],nodes[d],p);
break;
case 'T':
scanf("%d",&r);
if(nodes[r]->pr){
printf("Not root, break.\n");
break;
}
nodes[r]->data.print();
break;
case 'P':
scanf("%d",&r);
if(nodes[r]->pr){
printf("Not root, break.\n");
break;
}
n=nodes[r];
pop(n);
printf("New root:\n");
n->data.print();
break;
case 'A':
printf("Show all\n");
for(int i=0;i<now;++i) nodes[i]->data.print(),putchar('\n');
break;
case 'Q':
return 0;
}
}
return 0;
}