首页 > 代码库 > HDU 1890 Robotic Sort
HDU 1890 Robotic Sort
题意:
将一列数字排序 排序规则是 每次找到最小值的位置loc 将1~loc所有数字颠倒 然后删掉第一位 直到排好序 排序要求是稳定的
思路:
这题要做的是 寻找区间最小值位置 翻转区间 的操作 因此可以想到用splay
只需要每个节点记录一个small 就可以实现找到最小值位置
翻转区间操作就是将splay的超级头转到最上面使之成为根 再把loc转到根下面 这时根的右儿子的左儿子就是需要翻转的区间 用一个rev延迟更新 然后将loc转到最上面是指成为根 删掉根 如此循环
注意:
由于翻转区间这种更新会改变树的结构 因此无论是splay的时候还是做任何查找的时候都必须先把rev给down下去!!
代码:
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long LL; #define keytree ch[ch[root][1]][0] #define L(x) ch[x][0] #define R(x) ch[x][1] #define N 100010 int n,tot,root; int a[N],ch[N][2],pre[N],size[N],val[N],small[N],rev[N]; void newnode(int &u,int fa,int w) { u=++tot; L(u)=R(u)=0; pre[u]=fa; size[u]=1; small[u]=val[u]=w; rev[u]=0; } void up(int u) { size[u]=size[L(u)]+size[R(u)]+1; small[u]=min(val[u],min(small[L(u)],small[R(u)])); } void down(int u) { if(rev[u]) { if(L(u)) rev[L(u)]^=1; if(R(u)) rev[R(u)]^=1; swap(L(u),R(u)); rev[u]=0; } } void rotate(int u,int kind) { int fa=pre[u]; down(fa); down(u); ch[fa][!kind]=ch[u][kind]; pre[ch[u][kind]]=fa; if(pre[fa]) ch[pre[fa]][ch[pre[fa]][1]==fa]=u; pre[u]=pre[fa]; ch[u][kind]=fa; pre[fa]=u; up(fa); } void splay(int u,int goal) { int fa,kind; down(u); while(pre[u]!=goal) { if(pre[pre[u]]==goal) { down(pre[u]); down(u); rotate(u,L(pre[u])==u); } else { fa=pre[u]; down(pre[fa]); down(fa); down(u); kind=L(pre[fa])==fa; if(ch[fa][kind]==u) { rotate(u,!kind); rotate(u,kind); } else { rotate(fa,kind); rotate(u,kind); } } } up(u); if(goal==0) root=u; } int getkth(int u,int k) { down(u); int s=size[L(u)]+1; if(s==k) return u; if(s>k) return getkth(L(u),k); else return getkth(R(u),k-s); } void build(int &u,int l,int r,int fa) { if(l>r) return ; int mid=(l+r)>>1; newnode(u,fa,a[mid]); build(L(u),l,mid-1,u); build(R(u),mid+1,r,u); up(u); } void init() { root=tot=0; L(root)=R(root)=pre[root]=size[root]=rev[root]=0; val[root]=small[root]=N; newnode(root,0,N); newnode(R(root),root,N); build(keytree,1,n,R(root)); up(R(root)); up(root); } int getmin(int u,int x) { down(u); if(val[u]==x) return 1+size[L(u)]; if(small[L(u)]==x) return getmin(L(u),x); if(small[R(u)]==x) return size[L(u)]+1+getmin(R(u),x); } int getpre(int u) { down(u); u=L(u); down(u); while(R(u)) { u=R(u); down(u); } return u; } void remove() { if(L(root)) { int i=getpre(root); splay(i,root); R(i)=R(root); pre[R(root)]=i; root=L(root); pre[root]=0; up(root); } else { root=R(root); pre[root]=0; } } struct input { int val,id; bool operator<(const input fa) const { if(val==fa.val) return id<fa.id; return val<fa.val; } }fzc[N]; int main() { int i,loc; while(~scanf("%d",&n)) { if(!n) break; for(i=1;i<=n;i++) { scanf("%d",&fzc[i].val); fzc[i].id=i; } sort(fzc+1,fzc+n+1); for(i=1;i<=n;i++) a[fzc[i].id]=i; init(); for(i=1;i<n;i++) { loc=getmin(root,i); printf("%d ",loc+i-2); splay(getkth(root,1),0); splay(getkth(root,loc),root); rev[keytree]^=1; splay(getkth(root,loc),0); remove(); } printf("%d\n",n); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。