void rotate(int x) { int y = par[x],z = par[y],k = chk(x),w = ch[x][k^1]; ch[y][k] = w;par[w] = y; ch[z][chk(y)] = x;par[x] = z; ch[x][k^1] = y;par[y] = x; pushup(y);pushup(x); } //他改变了这棵树 void rotateback(int x) { int y = ch[x][chk(x)^1],z = par[x],k = chk(y),w = ch[y][k^1]; ch[x][k] = w;par[w] = x; ch[z][chk(x)] = y;par[y] = z; ch[y][k^1] = w;par[x] = y; pushup(x);pushup(y); } //他又改了回来 //原来只要把y和x互相改一下就行了... //chk : 子节点的方向 //ch[][2] : 存储该节点的儿子 //pushup:更新size信息 void splay(int x,int goal = 0) { while(par[x] != goal) { int y = par[x],z = par[y]; if(z != goal) { if(chk(x) == chk(y)) rotate(y); else rotate(x); } rotate(x); } if(!goal) root = x; } //他伸展了一棵树 void splayback(int x,int goal = 0) { int k = chk(x); while(ch[x][k] != goal) { int y = ch[x][k^1],z = ch[y][k^1]; if(z != goal) { if(z) rotateback(x); rotateback(y); } rotateback(y); } } //他又伸展了回来,这段代码似乎有问题