方知蓦然回首之时
那人却已不在灯火阑珊处

一道傻逼 LCT ,结果调了好久。

首先直接离线处理,发现询问在中间做和在最后做是一样的,相当于一棵一棵树扫过去用 LCT 动态维护一个区间换父亲的操作,考虑用 LCT 建虚点,搞一搞即可。

需要注意这题查询两点间的距离的时候不能直接 split 出来,因为 LCT 上的 LCA 有可能是虚点,从而忽略了虚 LCA 到实 LCA 中间一段距离对答案的贡献。同时还注意点小细节,比如 1 号点的范围 233 .

另外这题保证了操作合法,就没必要费力不讨好的每次都 get_root 一下了,否则可能会 TLE 飞 。。。

关于如何求 LCT 上的 LCA :对于 \operatorname{access} 操作保存下最后一次的 \operatorname{splay}y 。先 \operatorname{makeroot}(root) ,再 \operatorname{access}(u) ,最后 \operatorname{access}(v) 返回的值就是答案。

READ MORE

PKUWC 考挂的我只能争取省选翻盘了。

从寒假开始就没有再颓废过游戏了,唯一浪费时间的可能就是干了些工程向的东西。基本 follow 着 txc 和 zsy 的博客做题,有时旷掉考试

不知道这样的训练是否有用呢,ZJOI 会告诉我答案吧。

READ MORE

ZJOI 2019 了,机房同学也差不多都会基本多项式了,就写篇有关简单的多项式操作复习笔记吧 QAQ

约定:以下操作默认 n = \deg(F(x)) + 1 ,等号一般表示在 \bmod\ {x^n} 的意义下同余。

多项式乘法

可以先把多项式的系数转为点值,各位分别乘起来以后再插值出原多项式。考虑到单位根 / 原根的性质,我们有 FFT / NTT 。

READ MORE

c_0 / c_1 / c_? 表示举报序列中 0 / 1 / \text{?} 的数量。

  • 2^{c_?} 的做法,暴力枚举剩余位;
  • 2^{c_0} 的做法,FWT 预处理一遍,固定所有的 1 位,然后对 0 位进行容斥;
  • 2^{c_1} 的做法,FWT 预处理一遍,固定所有的 0 位,然后对 1 位进行容斥。

可以发现我们最后的复杂度即 O(n \log n + q \min(2^{c_0}, 2^{c_1}, 2^{c_?})) = O(n \log n + 2^6 q) 。可以通过此题。

READ MORE