noip2024

asdf。

开考前五分钟先看 T4，看了五分钟不会。

然后比赛开始了，把所有题都读了一遍，T1 感觉是贪心，T2 不知道，T3 不知道，T4 ds。

开 T1，想了一会，感觉先把占用过的贪掉，再从左到右贪就是对的，遂写

写完挂样例了，调了一会过了，大概是 30min 左右

调着调着发现我好像做烦了，直接从左到右贪应该就是对的，但是已经快过了，所以懒得改了。

然后开 T2，想了想感觉是很规矩的计数题，算了算写到代码里就过大样例了，大概花了 20min。

开 T3，想了一会不会，于是重新理了一下。

首先需要找到一种方式刻画这个结构，进行一些手模发现可以是一个链剖分的结构，而题目要求的东西也能在这上面体现

那么就可以直接 dp 了，在草稿纸上列了一下状态定义，以及一些转移，然后就开始写了

挂大样例了，感觉手调不是很会，而且迟早要拍，于是就写了个拍，用 $k=1$ 拍

拍出来了，调了一会调过了，大概还剩 2h。

开 T4，区间 lca 可以转，然后就是序列上的问题了，想了一会会了三维偏序的做法，但是 $5\times10^5$ 感觉不一定过的去，于是想想怎么优化

这个三维偏序的部分直接优化感觉不是很优前途，因此考虑找一下问题的性质，可以发现加入的区间是笛卡尔树结构的，因此更小的会顶替掉更大的，那么离线扫描线即可。

写完了大概还剩 1h 多一点，然后开始写拍。

给 T4 写拍，发现拍挂了，爆。

检查了一下发现有一点东西写挂了，使用的区间应该是不交的，但是实际上相交了，改完过拍了，大概还剩 40min

然后拍 T1，写了一个 next_permutation 暴力，拍 $n\le15$，拍挂了

代码太长不想调了，于是直接重构，写完了，过大样例了，又拍挂了。

仔细检查发现是暴力写挂了，写挂的还挺多，修完过拍了，大概剩 15min。

检查检查代码啥的就结束了。