网站建设设计时代创信好,南京怎么做网站,会计网站建设,云南省建设工程造价信息网官网正题
题目链接:https://www.luogu.com.cn/problem/U136336?contestId36038 题目大意
第iii次找到第iii大的数字位置xix_ixi并且翻转[i,xi][i,x_i][i,xi]#xff0c;求输出序列xxx 解题思路
记录一下每个排名在SplaySplaySplay中的位置#xff0c;然后暴力翻转即可。 …正题
题目链接:https://www.luogu.com.cn/problem/U136336?contestId36038 题目大意
第iii次找到第iii大的数字位置xix_ixi并且翻转[i,xi][i,x_i][i,xi]求输出序列xxx 解题思路
记录一下每个排名在SplaySplaySplay中的位置然后暴力翻转即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
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 yfa[x],zfa[y];int xsDirect(x),ysDirect(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 yfa[x];if(fa[y]z)Rotate(x);else if(Direct(x)Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}if(!z)rootx;return;
}
int rk(int x){Splay(x,0);return siz[t[x][0]];
}
int find(int x,int k){PushDown(x);if(ksiz[t[x][0]])return find(t[x][0],k);if(siz[t[x][0]]1k)return x;return find(t[x][1],k-siz[t[x][0]]-1);
}
bool cmp(int x,int y){if(val[x1]val[y1])return xy;return val[x1]val[y1];
}
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 i2;in1;i){scanf(%d,val[i]);t[i][0]i-1;fa[i-1]i;p[i-1]i-1;PushUp(i);}sort(p1,p1n,cmp);t[n2][0]n1;fa[n1]n2;PushUp(n2);rootn2;for(int i1;in;i){int wrk(p[i]1);printf(%d ,w);
// print(root);putchar(\n);int xfind(root,i),yfind(root,w2);Splay(x,0);Splay(y,x); rev(t[y][0]);
// print(root);putchar(\n);}return 0;
}
