Splay本来常数就大，写丑了跑得慢很正常
by qwqKanade @ 2018-01-28 07:07:10
@[v天下第柒v](/space/show?uid=50202) 多谢dalao，但是蒟蒻还是疑惑：为啥别人写的splay跑那么快，我这个怎么跟西方记者那样慢，是哪里写挂了？
by GoldenPotato137 @ 2018-01-28 07:54:47
@[GoldenPotato](/space/show?uid=52563) 只是总体常数比较大。卡卡常，能快个一倍
by qwqKanade @ 2018-01-28 07:58:27
@[GoldenPotato](/space/show?uid=52563) 我的其它部分都和你差不多，应该是你的旋转常数大了..（我是不是在挖坟Orz）
```
void rotate(int x)
{
int y=s[x].fa;
int z=s[y].fa;
int k=x==s[y].ch[1];
s[z].ch[y==s[z].ch[1]]=x;
s[x].fa=z;
s[y].ch[k]=s[x].ch[k^1];
s[s[x].ch[k^1]].fa=y;
s[x].ch[k^1]=y;
s[y].fa=x;
pushup(y);
pushup(x);
}
void Splay(int x,int goal)
{
while (s[x].fa!=goal)
{
int y=s[x].fa;
int z=s[y].fa;
if (z!=goal)
{
(x==s[y].ch[0])^(y==s[z].ch[0])?rotate(x):rotate(y);
}
rotate(x);
}
if (goal==0)
{
root=x;
}
}
```
by ouuan @ 2018-09-29 11:37:02
@[ouuan](/space/show?uid=49742) 多谢回复。
但是我去康过了，我的旋转和你的基本上一样呀。
by GoldenPotato137 @ 2018-10-11 21:08:17
@[GoldenPotato](/space/show?uid=52563) 又不是WA了，常数问题本来就应该代码长得差不多吧..只不过我也不知道是不是这里的问题..但Splay大部分时间都在旋转，旋转常数稍大一点影响蛮大的。
by ouuan @ 2018-10-11 21:16:38
@[GoldenPotato](/space/show?uid=52563) 还有一个问题，就是你用的是多个数组，貌似结构体会快一些，因为内存连续？好像听说过这种玄学。
by ouuan @ 2018-10-11 21:18:38