2212: [Poi2011]Tree Rotations
stupid_lulu
posted @ 2013年3月18日 21:34
in poi
, 1305 阅读
这题其实是道水题。。平衡树的启发式合并。总的逆序对个数=左子树的+右子树的+左子树与右子树之间的。。
然后暴力合并。。每次合并时计算左右子树间的逆序对,而左右子树的之前已经递归求好了。。这次得了个教训,果然旋转还是比不旋转强= =!
#include<cstdio> typedef long long ll; struct re{ int n,c[3],f; long long s; } t[300001]; int n,sum=0,s=0; ll ans=0,ss=0; int root[1000001]; ll min(ll a,ll b){return a<b? a:b;} void update(int x){ t[x].s=t[t[x].c[1]].s+1+t[t[x].c[2]].s; } void ro(int x,int w){ int y=t[x].f; int ww=3-w; t[y].c[ww]=t[x].c[w]; if (t[x].c[w]) t[t[x].c[w]].f=y; t[x].f=t[y].f; if (t[y].f){ int z=t[y].f; if (y==t[z].c[1]) t[z].c[1]=x; else t[z].c[2]=x; } t[y].f=x; t[x].c[w]=y; update(y); } void splay(int i,int x){ while (t[x].f){ int y=t[x].f; if (!t[y].f){ if (x==t[y].c[1]) ro(x,2); else ro(x,1); }else{ int z=t[y].f; if (y==t[z].c[1]){ if (x==t[y].c[1]){ro(y,2); ro(x,2);} else {ro(x,1); ro(x,2);} }else{ if (x==t[y].c[2]){ro(y,1); ro(x,1);} else {ro(x,2); ro(x,1);} } } } update(x); if (!t[x].f) root[i]=x; } void inse(int i,int x,int y){ ll su=0; while (true){ t[x].s++; if ((t[y].n<t[x].n&&t[x].c[1]==0)||(t[y].n>t[x].n&&t[x].c[2]==0)) break; if (t[y].n<t[x].n) x=t[x].c[1]; else {su+=t[t[x].c[1]].s+1; x=t[x].c[2];} } if (t[y].n<t[x].n) t[x].c[1]=y; else{su+=t[t[x].c[1]].s+1; t[x].c[2]=y;} t[y].f=x; ss+=su; splay(i,y); } void uniont(int i,int x){ int l=t[x].c[1],r=t[x].c[2]; if (r) uniont(i,r); t[x].f=t[x].c[1]=t[x].c[2]=0; t[x].s=1; inse(i,root[i],x); if (l) uniont(i,l); } void combine(int k,int i,int j){ int x=root[i]; int y=root[j]; if (t[x].s<t[y].s){ uniont(j,root[i]); root[k]=root[j]; }else{ uniont(i,root[j]); root[k]=root[i]; } } void dfs(int i){ int x; scanf("%d",&x); if (x!=0){ t[++sum].n=x; t[sum].s=1; root[i]=sum; return; } int l=++s,r=++s; dfs(l); dfs(r); ss=0; ll sa=t[root[l]].s*t[root[r]].s; combine(i,l,r); ans+=min(ss,sa-ss); } int main(){ scanf("%d",&n); s=1; dfs(1); printf("%lld\n",ans); }
2024年2月22日 00:12
I truly welcome the basic imagining that went into this blog. Shows signs of improvement and bette