启发式合并
这两天做了两道“启发式合并”的题，似乎“启发式合并”就是每次把节点数小的依次放到节点数大的地方，对只有合并操作的题能做到logn的时间复杂度
[BZOJ1483][HNOI2009]梦幻布丁：链表的启发式合并
每次把短的安到长的上面再判断
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include<cstdio>#define N 1111111using namespace std;int n,m,i,ii,p,ans,x,y,t,tmp,a[N],now[N],first[N],next[N],color[N],ft[N];int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%d",&a[i]); color[a[i]]++; ft[a[i]]=a[i]; if(a[i]!=a[i-1])ans++; if(!first[a[i]])first[a[i]]=i; next[now[a[i]]]=i; now[a[i]]=i; } for(ii=1;ii<=m;ii++){ scanf("%d",&p); if(p==2)printf("%d\n",ans);else{ scanf("%d%d",&x,&y); if(x==y)continue; if(color[ft[x]]>color[ft[y]])t=ft[x],ft[x]=ft[y],ft[y]=t; x=ft[x];y=ft[y]; if(color[x]==0)continue; for(i=first[x];i;i=next[i]){ tmp=i; if(a[i+1]==y)ans--; if(a[i-1]==y)ans--; } for(i=first[x];i;i=next[i])a[i]=y; next[tmp]=first[y];first[y]=first[x]; color[y]+=color[x];first[x]=color[x]=0; } }} |
[BZOJ2733][HNOI2012]永无乡：Splay的启发式合并
每次把小的Splay暴力拆掉，加入到大的Splay上面，第一次写无根Splay、、
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include<cstdio>#include<iostream>#define N 111111using namespace std;int n,m,T,x,y,p,q,k,i,top,father[N],son[N][2],size[N],val[N],num[N],zhi[N];char s[9];int find(int x){while(father[x])x=father[x];return x;}void pushup(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;}void newnode(int x,int fa,int da){father[x]=fa;size[x]=1;val[x]=da;son[x][0]=son[x][1]=0;}void rotate(int x,int k){ int y=father[x]; son[y][!k]=son[x][k];father[son[y][!k]]=y; son[father[y]][son[father[y]][1]==y]=x; father[x]=father[y]; son[x][k]=y;father[y]=x; pushup(y);}void splay(int x){ while(father[x]){ int y=father[x],z=father[y],f=(son[z][0]==y); if(!z)rotate(x,son[y][0]==x);else{ if(son[y][f]==x)rotate(x,!f);else rotate(y,f); rotate(x,f); } } pushup(x);}void insert(int x,int number,int key){ while(son[x][key>val[x]])size[x]++,x=son[x][key>val[x]]; size[x]++;son[x][key>val[x]]=number; newnode(number,x,key); splay(number);}void intour(int x){ if(!x)return;num[++top]=x;zhi[top]=val[x]; intour(son[x][0]);intour(son[x][1]);}int find(int x,int k){ if(size[son[x][0]]+1==k)return x; if(size[son[x][0]]>=k)return find(son[x][0],k); return find(son[x][1],k-size[son[x][0]]-1);}void link(){ scanf("%d%d",&x,&y);p=find(x);q=find(y); if(p!=q){ if(size[p]>size[q])swap(p,q),swap(x,y); top=0;intour(p); for(int i=1;i<=top;i++)insert(q,num[i],zhi[i]); }}int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",&val[i]),size[i]=1; for(i=1;i<=m;i++)link(); scanf("%d",&T); while(T--){ scanf("%s",s); if(s[0]=='B')link();else{ scanf("%d%d",&x,&k); splay(x); if(k>size[x])puts("-1");else printf("%d\n",find(x,k)); } }} |
似乎启发式合并都是HNOI的，看来ZJOI是不会考这么简单的题目的、、
2015年6月17日 06:51
时间复杂度证明你会么。。