NOI 2018 网络同步赛。
（听说 dzd 讲话很赛艇，听说社会活动很…？）
开幕式讲课全程 B 站直播好评！
Day 1
听说 NOI T1 会是简单题。
本质上就是与询问点连通的点中离 1 号点的最近点。
看起来可持久化并查集可做（虽然是两个 的）。
可能是因为太久没写主席树，写了一个小时，但是到三个小时的时候才调出来。（隔壁机房在装修，声音大到心态爆炸）
测了一发，-O2 4.1s，稍微卡了卡常，加个快读，卡到 4.01s，感觉再怎么卡下去后面两题要来不及，想想也就 10 分，看 T2。
看题的时候就感觉 T2 不会做。交换次数就是逆序对，然后观察了一波提示中的反例 3 2 1，感觉就是每个数字的移动方向不能变化，那么就不能有“超车”的现象。然后就能设计状压了，f[mask][0/1] 表示选了哪些数，和原排列的大小关系。转移时枚举下一位的数判断是否合法。
还有 1h 15min。
然后是 T3，一看就是 SAM 题。一组询问就是广义 SAM 上跑，统计新建结点对答案的贡献。然后我就感觉把所有串扔进去复杂度（其实是正确性）不对。然后就感觉是要把 SAM 可持久化。
（实际上 SAM 能不能可持久化，或者说能不能很方便地可持久化是个问题）
试图打了个然后搞不出来，然后每次暴力复制 SAM，去搞前 7 个点。然后防止 MLE，又把数组开小点。（不知道在想些什么。。。）
吃完饭，说是可以查成绩了，T1 3.5s AC，然后 T3 把数组开小了 RE20。（一直以为那两个点是 的）100 + 44 + 20 = 164。
听说现场赛那边分都不是特别高，zzy 210, zrf 180, fls ~200。
后来听说 lsk 240+, %%%
听说 T1 卡 SPFA，幸好习惯写 dijkstra。
比赛的时候个人认为可持久化并查集可以写成 1 个 ，就是试图把每次在线段树上定位的 优化掉。也可以用 kruskal 重构树，就是将并查集合并过程描述成二叉树的形式（新建结点表示新连通块，合并的两个连通块的结点分别表示左右子树），询问时在树上二分得到对应的连通块。
晚上讨论/撕烤了一下，T3 其实只要用一个指针模拟建广义 SAM 的过程，在这个同时统计每个右端点对应的非法子串的长度范围。（DFS 序 + 主席树）最后建出询问串的 SAM 统计一下
（另外，那根本不是可持久化，只要支持撤销就可以了。所以只要维护哪些结点被修改了，一次询问结束后再覆盖回去。。。）
然后对于 T2，如果再推一下那个结论，就会发现它等价于最长下降子序列至多为 2。然后设计 DP f[i][j] 表示处理到第 位，剩下的数中 个比前 个中的最大值大。转移考虑选取比最大值的大的数，或者选最小值（如果选其它的就会出现长度为 3 的下降序列）。然后可以发现这是三角形区域的随机游走，用类似 Catalan 数的方式，可以用两个组合数表示。最后扫一遍原数组，枚举哪一位开始字典序开始严格大于原串，求出对应的状态即可。
Day 2
（好像听王宏说 Day2 有最简单的题和最难的题？？？）
T1 看完题面，发现每个数对应的攻击值是固定的，拿个 std::multiset 搞，然后就变成了 个同余方程。我先全部解出来，然后再 CRT 合并（说是 CRT，直接暴力列方程 exgcd 的）。中间爆long long, 又因为个思博 undefined-behavior 调了一会。（话说 -ftrapv 好呀，一下就看出爆 long long 了）
这时，机房突然停电！
T3 是吉利题，（虽然不是计算几何，）表示不敢做。来看 T2。
T2 有点猫锟色彩（TAC CAT ?），但也不会乱搞。（CTSC 的时候他不是说不出最优化了吗？）
机房突然来电又突然停电。再次来电之后，赶紧把代码搞到笔记本上（但是后来就没有断电了）。还有 2h 20min。
这时有 T3 20 分状压，T2 15 分暴力 + 15 分扫描线 + 线段树 + 15 分暴力树剖。感觉把它们全部打完就差不多了。于是开始狂码，幸好调得不多，还剩 20 分钟的时候基本调完。（T2 大样例真良心）
回头查了一遍 T1。
成绩还要 20 年才能出（2037），先去看讲评。T1 LCA 说中间结果也可以不爆 long long。T2 果真是猫锟出的（松松松验题+讲题），出了半年的题，神奇的大样例解释。T3 std 10k。。。
然后数据就出来了，LOJ 还在传题。本地测了一发。100 + 30 + 20 = 150。T2 如此强的样例却发现不了我数组开小了！（MAXN 和 MAXM 打反。。。）
总结
这次 NOI，个人感觉~~题目难度适中，覆盖知识点广，有贴合实际的背景，解法比较自然，给出题人点个赞！~~依然延续了打暴力竞赛的传统。
如果只 A 两天 T1，其余题都打暴力（像我），有 164 + 150 = 314。加上鄙视笔试 100 分，对应现场赛排名，有前 100。如果两天 8 + 15 = 23 分没有爆掉是 337, 好像正好是 Au 线（如果笔试挂那就没办法了）
如果 D1T1 调得快一点，T3 的 68 分可能可以出来，那就进集训队线了(我怎么菜，怎么可能进队呢)
当然，以上为理论得分。毕竟实际在比赛过程中，对题目难度不确定，心态，以及手速，RP 等各种因素都会影响这些暴力打不打得出来，打不打得对。
比如说像两天爆掉的 23 分，就很不应该，D1 的 8 分只要看一眼题面就能发现，D2 也只要造一组大数据就可以（调完还有 20 分钟，应该是发现得了的）。所以小数据验证正确性，大数据验证复杂度和数组越界都是十分必须的。
另外， D1T1 调题速度极慢，严重影响做后面两题。
但是无论如何，这总比 UNR FST 3 题要好。
另外，现场赛这边，zzy rk9 进队， lsk 和 cyz 都上了集训队线（可惜是 D 类），fls 贴线进队，zrf 遗憾 Ag，苟利和 wcz 也是 Ag。
最神奇的是，浙江 A 队除 zzy 外，全部爆炸。求吉老师心理阴影面积。。。
