我红温了，为了学 LCT，我得先学这个 Splay，

等我照着 oiwiki 学完 Splay 之后发现 Splay 查询排名的部分时间复杂度假了。

下面是 hack 程序

#include <bits/extc++.h>

#define inline __always_inline
const int n = 1e5, m = 5e4;

int main()
{
	freopen64("hack.in", "w", stdout);
	printf("%d\n", n);
	for (int i = 1; i <= m; i++)
		printf("1 %d\n", i);
	for (int i = m + 1; i <= n; i++)
		printf("3 0\n");
	return 0;
}

在做完插入之后树的形态是一条链，如果说之后的查询每次都 splay 稳住树的形态还好说，但 $0$ 不是树的元素，而 oi-wiki 的代码：

int rk(int k) {
  int res = 0, cur = rt;
  while (1) {
    if (k < val[cur]) {
      cur = ch[cur][0];
    } else {
      res += sz[ch[cur][0]];
      if (!cur) return res + 1;		// 我红温了
      if (k == val[cur]) {
        splay(cur);
        return res + 1;
      }
      res += cnt[cur];
      cur = ch[cur][1];
    }
  }
}

漂亮，抬走吧，没救了。

所以我这个 hack 成功的 hack 了我的提交记录

大半夜发现模板的代码出锅真的太崩溃了，文化课作业还一点没写，QAQ