首页 > 代码库 > 【Splay】Codeforces Round #424 (Div. 1, rated, based on VK Cup Finals) B. Cards Sorting
【Splay】Codeforces Round #424 (Div. 1, rated, based on VK Cup Finals) B. Cards Sorting
Splay要支持找最左侧的最小值所在的位置。类似线段树一样处理一下,如果左子树最小值等于全局最小值,就查左子树;否则如果当前节点等于全局最小值,就查当前节点;否则查右子树。
为了统计答案,当然还得维护子树大小的函数。
找到位置以后,直接将左右子树交换即可。不需要打标记。
删除节点时,直接将其前驱(是指序列下标的前驱,就是将待删除节点Splay到根后,左子树的最右节点)Splay到根,将其后继(类似)Splay到根的儿子。
然后将后继的左儿子删除即可。
别忘了及时Maintain();
这份代码的Maintain()时机都很合理,以后不要怀疑了。
但是如果插入是单调的,我这个代码好像有点问题……被卡掉了。于是我就在插入的过程中加入了随机Splay结点到根的操作。就过了
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; #define maxn 100010 #define INF 2147483647 int fa[maxn],val[maxn],c[maxn][2],root,tot,siz[maxn],cnt[maxn],val2[maxn]; int minv[maxn]; void Maintain(int x) { siz[x]=siz[c[x][0]]+siz[c[x][1]]+cnt[x]; minv[x]=val2[x]; if(c[x][0]){ minv[x]=min(minv[x],minv[c[x][0]]); } if(c[x][1]){ minv[x]=min(minv[x],minv[c[x][1]]); } } int Findminp(int x=root){ while(1){ if(c[x][0] && minv[c[x][0]]==minv[root]){ x=c[x][0]; } else if(val2[x]==minv[root]){ return x; } else{ x=c[x][1]; } } } void NewNode(int &x,int Fa,int key,int key2) { x=++tot; fa[x]=Fa; c[x][0]=c[x][1]=0; val[x]=key; val2[x]=minv[x]=key2; siz[x]=cnt[x]=1; } void Rotate(int x,bool flag) { int y=fa[x]; // pushdown(y); // pushdown(x); c[y][!flag]=c[x][flag]; fa[c[x][flag]]=y; if(fa[y]){ c[fa[y]][c[fa[y]][1]==y]=x; } fa[x]=fa[y]; c[x][flag]=y; fa[y]=x; Maintain(y); } void Splay(int x,int goal) { if(!x || x==goal){ return; } // pushdown(x); int y; while((y=fa[x])!=goal){ if(fa[y]==goal){ Rotate(x,c[y][0]==x); } else{ if((c[y][0]==x)==(c[fa[y]][0]==y)){ Rotate(y,c[fa[y]][0]==y); } else{ Rotate(x,c[y][0]==x); y=fa[x]; } Rotate(x,c[y][0]==x); } } Maintain(x); if(!goal){ root=x; } } int Find(int key,int x=root) { while(c[x][val[x]<key]){ if(val[x]==key){ return x; } x=c[x][val[x]<key]; } return x; } void Insert(int key,int key2) { if(!root){ NewNode(root,0,key,key2); return; } int x=Find(key); if(val[x]==key){ ++cnt[x]; Splay(x,0); return; } NewNode(c[x][val[x]<key],x,key,key2); Splay(c[x][val[x]<key],0); } int Findmax(int x=root) { while(c[x][1]){ x=c[x][1]; } return x; } int Findmin(int x=root) { while(c[x][0]){ x=c[x][0]; } return x; } //int GetPre(int x) //{ // Splay(x,0); // return Findmax(c[x][0]); //} //int GetNex(int x){ // Splay(x,0); // return Findmin(c[x][1]); //} int n,m; typedef long long ll; ll ans; int main(){ scanf("%d",&n); int x; srand(233); for(int i=1;i<=n;++i){ scanf("%d",&x); Insert(i,x); Splay(rand()%i+1,0); } for(int i=1;i<=n;++i){ int p=Findminp(); Splay(p,0); ans+=(ll)(siz[c[p][0]]+1); swap(c[p][0],c[p][1]); int pPre=Findmax(c[p][0]); int pNex=Findmin(c[p][1]); if(!pPre && pNex){ root=c[p][1]; fa[root]=0; } else if(pPre && !pNex){ root=c[p][0]; fa[root]=0; } else if(pPre && pNex){ Splay(pPre,0); Splay(pNex,pPre); c[pNex][0]=0; Maintain(pNex); Maintain(pPre); } } printf("%I64d\n",ans); return 0; }
【Splay】Codeforces Round #424 (Div. 1, rated, based on VK Cup Finals) B. Cards Sorting
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。