正题
题目链接:https://www.luogu.com.cn/problem/U136336?contestId=36038
题目大意
第 i i i次找到第 i i i大的数字位置 x i x_i xi并且翻转 [ i , x i ] [i,x_i] [i,xi],求输出序列 x x x
解题思路
记录一下每个排名在 S p l a y Splay Splay中的位置,然后暴力翻转即可。
c o d e code code
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; int n,root,t[N][2],val[N],p[N],siz[N],fa[N],r[N]; bool Direct(int x) {return t[fa[x]][1]==x;} void Connect(int x,int y,int dir) {t[x][dir]=y;fa[y]=x;return;} void PushUp(int x) {siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return;} void rev(int x){ swap(t[x][0],t[x][1]); r[x]^=1;return; } void PushDown(int x){ if(!r[x])return; rev(t[x][0]);rev(t[x][1]); r[x]=0;return; } void Rotate(int x){ PushDown(fa[x]);PushDown(x); int y=fa[x],z=fa[y]; int xs=Direct(x),ys=Direct(y); Connect(y,t[x][xs^1],xs); Connect(x,y,xs^1); Connect(z,x,ys); PushUp(y);PushUp(x); return; } void Downdata(int x){ if(!x)return; Downdata(fa[x]); PushDown(x); return; } void Splay(int x,int z){ Downdata(x); while(fa[x]!=z){ int y=fa[x]; if(fa[y]==z)Rotate(x); else if(Direct(x)==Direct(y)) Rotate(y),Rotate(x); else Rotate(x),Rotate(x); } if(!z)root=x; return; } int rk(int x){ Splay(x,0); return siz[t[x][0]]; } int find(int x,int k){ PushDown(x); if(k<=siz[t[x][0]])return find(t[x][0],k); if(siz[t[x][0]]+1==k)return x; return find(t[x][1],k-siz[t[x][0]]-1); } bool cmp(int x,int y){ if(val[x+1]==val[y+1])return x<y; return val[x+1]<val[y+1]; } void print(int x){ if(!x)return; print(t[x][0]); printf("%d ",val[x]); print(t[x][1]); } int main() { freopen("31.in","r",stdin); freopen("data.out","w",stdout); scanf("%d",&n);siz[1]=1; for(int i=2;i<=n+1;i++){ scanf("%d",&val[i]); t[i][0]=i-1;fa[i-1]=i; p[i-1]=i-1;PushUp(i); } sort(p+1,p+1+n,cmp); t[n+2][0]=n+1;fa[n+1]=n+2; PushUp(n+2);root=n+2; for(int i=1;i<=n;i++){ int w=rk(p[i]+1); printf("%d ",w); // print(root);putchar('n'); int x=find(root,i),y=find(root,w+2); Splay(x,0); Splay(y,x); rev(t[y][0]); // print(root);putchar('n'); } return 0; }
c/c++开发分享[2020.10.25NOIP模拟赛]序列【Splay】地址:https://blog.csdn.net/Mr_wuyongcong/article/details/109276339
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/597084.html