noip2025邮寄

体测，上午一直在紧张。然后中午练了一下跳远直接导致腹肌酸痛。然后跑 1000m 的时候腿一直是软的，还好最后有望及格。

体测完右膝倒闭了，上厕所都会痛，于是停止打球。

遭遇感冒，回家 lululu 了 $3$ 天。一直在培养张勤健，但是打不过 alex_liu。

没睡好，但还算精神。

压缩密码很诡异，由于无法分辨；和：解压时吃了一发罚时。

A 不太一眼，但是想了 2min 发现只会选最小的 $x+y$，其余的 $x$ 只用看选不选，那排个序枚举一下就完了。先不急着写。

B 比想象中的难。观察一会发现是先排序，如果有 $i<j<k$ 满足 $2a_j>a_k,a_i+a_j<a_k$，且 $k$ 是最大的不选的，$j$ 是最小的选的，就不合法。想的不太清楚，先扔了。

9:00 左右看完了 CD 题面，被吓哭了，先不做。然后 5min 左右写了 A。监考老师说 cmd 坏了，要用虚拟机来 diff？？？那我不会 linux 咋办啊。还好 A 容易肉眼比较。后面想了一下发现 B 枚举 $j,k$ 就好做了，容易 $O(n^2)$。9:30 左右写完，这个没 cmd 我真没招了，肉眼随机比对了一些行，假装过了。

然后感觉 C 这种题已经不在我的能力范围内了。然后开始想 D。发现部分分很少，考虑特殊性质。发现特殊性质 D 可以对每个点找到以它为左右端点的答案，然后只需要用到这些区间，就是每次询问 $O(n)$ 个区间 checkmax。那没有特殊性质也可以先处理 $l=2^i,r=2^j$ 的答案，然后只要查询 $2$ 个区间即可。那只要解决 $O(n)$ 次区间 checkmax。发现可以只考虑左端点 $\in[i-l+1,i]$ 和右端点 $\in[i,i+l-1]$ 的所有答案就可以了。可以做到 $O(n\log^2n+qn)$，如果你喜欢的话可以写 $n$ 个 st 表做到 $O(n\log n\log\log n+qn)$。

10:30 左右写完，大样例 3.3s，不会卡这个的常，假装能过。2.5h 大战 C，能赢吗。

反正最后是没有赢。每个点可以选择孝敬它的某一个祖先，或者取到子树的较大值。那么是 $f_{u,x,y}$ 表示 $u$ 子树内选了 $x$ 个点孝敬，$\text{mex}=y$ 的答案，转移类似树上背包 $O(n^3)$。然后随便拼了 $m=2$，时间就差不多到了。我也不知道我最后写的是不是 $O(n^3)$，不管了。

最后是 $100+100+[40,56]+[65,100]=[305,356]$，别挂分。

upd：复现了一下 D 考场代码，民间数据 95pts，倒闭。发现我把其中两个单调队列换成 st 表后快了一万倍，然后就能过了/yun

现在我决定把 CTT 邮寄也放在这里，时间仍以 noip 当天为 day1。

觉得自己膝盖好了，于是下午打了个球，然后又开始疼了。

前往北京。我弟说要送我去机场，但是他疑似感染了诺如病毒，然后在路上/tuu我身上了，导致我舍弃了一条裤子在车上。

飞机餐一如既往地难以下咽，勉强吃了些沙拉和果冻。然后快下飞机的时候感觉很想吐，怕不是被传染了，不好笑。

晚上吃了~老北京~涮羊肉，不知道地不地道，吃完以后就不觉得想吐了。

报到，室友是 $9$ 字母下划线 $4$ 字母。下午进行了试机，被 BC 击败了。本地机子很快，1e8 线性筛仅需 300ms-，但是 oj 疑似慢一些，然后在开营仪式上见到了张勤健。我疑似有点拉肚子。

困昏了。降温严重，走去机房的路上感觉全身都被冷空气打穿了。

一开场就肚子疼，但是在 WC 思考到了 t1 的 $O(nq)$ 做法。回来后迅速地写了。然后考虑上数据结构优化，然后我怎么不会优化啊。周围人都在哐哐写代码，那我咋办。想到自己可是省集 $10$ 场会 $0$ 题的人，好像不会这个题也没啥是吧。

t2 是字符串，t3 看起来是数论。t2 思考了若干假做法，感觉自己一点字符串都不会，很快就决定滚蛋。t3 范围很像根号老哥，部分分则是往根号分治方向启发。于是考虑根号分治，首先会了个 $O(n^{\frac 34})$，但怎么数据范围只有 $10^6$ 和 $10^{13}$ 啊，完全不给机会。后面仔细思考到了一个 $O(n^\frac 23)$ 做法，看起来比较有前途，至少可以通过所有部分分，冲。

把一个题拆成 $3$ 个题导致写了很久，终于在某个时刻获得了 60 分。然后卡常卡常卡卡时间到了。然后一直卡到了比赛结束。最后本地极限数据已经跑进 3s 了，但是 oj 比较慢，所以无法通过。只能说该给个 $10^{12}$ 的分的。

最后 $45+50+60=155$，成为拼好分选手（t1 和 t2 甚至各有 10 分没拼），那可能是拼坏分选手。

昨晚睡太晚了，导致起来的时候头晕。

又是不会 ABC，上来想了很久 A 怎么做。先想第一问，过了很久才会 $n=1$，然后发现 $\gcd(n,m)=1$ 时可以分开算完再合并。$\gcd(n,m)>1$ 想了很久都不会。感觉只有群论大手子能做出来。

然后观察了一下 B，很快会了结论，但怎么又不会维护。暴力好像很多，于是拼好分。

C 长得很像线性代数大手子题，打了 $30$ 跑路。

最后 $29.5+70+30=129.5$。

出来发现 BC 都被过穿了，C 怎么是诈骗题，我真没救了。

考完听说 noip 出分了，获得 $100+100+56+75=331$，怎么 CCF 神机没有护送我通过 t4？

睡得早了一些，但是起来还是很困/yun

A 居然是可做题，但是不会 1log，但是 2log 轻松通过了。

然后开始 lululu，经过漫长思考会了 B 单次询问 $O(L\sqrt L)$，但是空间很爆炸，感觉不应该写这个。于是又进行了漫长思考，但是啥也没研究出来。最后写了个这个东西，居然获得 $61$ 分，那不做了。

然后做 C，部分分不太多，并且我咋都不太会啊。先思考 $p=2$，发现可以把 or 干掉，然后 popcount 是很少的，可以直接枚举，那么只有 $O(d^2)$ 种值。然后 $(A,B,C)$ 固定的时候就是要搞一些二位数点。此时我认为要做 $qd^2$ 次二位数点，直接做不一定能过，也不太好写。然后又经过漫长思考，发现二元组的顺序好像也只有 $O(d^2)$ 种，那就是对 $2^dd^4$ 个点做 $qd^2$ 次二位数点。咬咬牙不知道能不能过。写了一半发现只用查 $q$ 次，那不是直接平衡到 $O(2^dd^4+q\sqrt{n})$ 了？高达 $73$ 分，开写。

最后没写完，$100+61+0=161$。

讲评时发现我 B 其实是单次线性的，然后最后正解是 $O(L\sqrt{L})$ 的，不知道我这个能不能改过去。然后 C 确实是这么做的，$p=3$ 时也只有 $1000$ 多种顺序，但是 $d$ 比较小所以上述做法也能通过。