LCT常数太大了，应该是过不去的
by Great_Influence @ 2019-01-03 20:06:41
@[Great_Influence](/space/show?uid=7035) 欺负人嘤嘤嘤
by ButterflyDew @ 2019-01-03 20:08:35
@[ButterflyDew](/space/show?uid=63727)
首先说明一下我造数据的时候没想着卡lct，毕竟一个$O(nlogn)$的算法我卡它就成duliu了
然后第一版数据是选择100个轻边深度最大的点修改
但是各人的树剖写法不一样啊这怎么卡呢？
正常人写出来的树剖，如果一堆树的size相等那么重儿子一定是邻接表最后一个或者第一个点，取决于你的写法
所以我就两种剖分的树剖都卡了一遍
看到这里你也明白了，树剖想过随机剖分重儿子+random_shuffle边+每个重链开zkw就过了
然后你也发现这对lct是个贼棒的消息，splay在访问同一个点的时候速度会加速，所以不是你lct常数小是数据对lct有利
by shadowice1984 @ 2019-01-03 20:12:16
@[shadowice1984](/space/show?uid=56384) 但好像很多我这样的大常数lct都过不去哎
by ButterflyDew @ 2019-01-03 20:17:46
@[ButterflyDew](/space/show?uid=63727)
后来呢？
你可以看评论区啊，一群人树剖和lct过了然后说自己常数小什么树剖卡不掉云云……
这里手动 @[陈枫](/space/show?uid=52299)
然后更加gg的是lct居然拿了这题的rk1……
哇哇哇我好气啊
原来怕卡io所以n+m=2e6，输出量是1e6，然后标程用的是getchar咸读，对于树剖最坏的数据标程700ms但是时限是3000ms
后来发现写树剖和lct的老哥一个个都精通fread和fwrite啊，都有这东西了我怕什么卡io啊
索性n=5e5,m=3e6，然后每个点询问6遍
这样不管你树剖再神仙都得给我tle
然后lct由于splay不是很能应付随机访问就tle了
~~这样的副作用就是会误伤绝大部分的正解就是了~~
by shadowice1984 @ 2019-01-03 20:18:17
@[shadowice1984](/space/show?uid=56384) ~~您不毒瘤吗~~
by NaCly_Fish @ 2019-01-03 20:19:44
@[shadowice1984](/space/show?uid=56384) 突然发现没有fwrite，赶紧去抄一个emm
by ButterflyDew @ 2019-01-03 20:20:23
@[NaCly_Fish](/space/show?uid=115864)
都是乱搞选手太nb了
要是嫌这题卡常就怪写树剖和lct的老哥太能乱搞了
by shadowice1984 @ 2019-01-03 20:21:54
电脑太卡..溜了
卡不动啊..
by ButterflyDew @ 2019-01-03 20:30:11
@[ButterflyDew](/space/show?uid=63727)
顺便说一句我测试的时候发现rk1老哥的lct都过不去……
STO 卡常神仙 Orz
by shadowice1984 @ 2019-01-03 20:32:44