又得吃Rating咯awa

T1 序列

正常难度，大概四十分钟左右解决了ovo

本题正解思路小总结：

• 由题意，需要找到最长的子序列，使得两端值严格大于中间所有值。可以枚举作为最大值的右端点 $m$，并寻找最长的合法中间部分。
• 预处理出每个值 $m$ 的左侧合法边界 $l[m]$ 和右侧合法边界 $r[m]$，即左右两侧第一个大于 $m$ 的元素位置。
• 从小到大枚举值 $m$，利用树状数组维护已遍历过的值（即所有小于 $m$ 的值）在原排列中的位置。
• 对于当前值 $m$，设其位置为 $pos[m]$。若其作为右端点，合法左端点位置应在 $l[m]$ 右侧，查询区间 $(l[m], pos[m])$ 内已加入的个数 $cnt$，则序列长度为 $cnt + 2$。
• 若其作为左端点，合法右端点位置应在 $r[m]$ 左侧，查询区间 $(pos[m], r[m])$ 内已加入的个数 $cnt$，同样更新长度为 $cnt + 2$。
• 遍历过程中不断更新最大长度，并将 $pos[m]$ 加入树状数组，最终得到的就是满足条件的最长子序列长度。

100pts

T2 树

哎，这题我可真是有很多话要讲了。

这题难度还是蛮高的，按道理来说我应该是做不出来滴。。。

但是我不知道怎么的就突然（其实用了俩小时qwq）发现了一个能够用随机化の解法（随机化万岁）

于是也是直接尝试写了个正解。

毕竟好不容易写了个正解出来，肯定是要保证大样例要过掉哒~

于是呢去洛谷把大数据全部传上去了，并进行了一波评测（懒得写文件比较qwq）

看到全过了也是心中狂喜：我居然能够过NOIP模拟赛T2？？？

15pts

哦不不不这无疑是难绷的。

赛后一直找不到自己究竟错在哪，于是问了问D老师

哦不不不这无疑是更加难绷的。（全机房最唐之人：写错一个符号丢了85pts）

为什么7个大样例没有一个测出来啊。？

没招了，比赛都打完了也没法回到过去了qwq

订正

本题正解思路小总结：

• 对每个节点建立主席树 $root[u]$，维护从根到 $u$ 的路径上各颜色的哈希值，颜色 $c$ 的权值为随机数 $w[c]$，插入时累加 $w[c]$。
• 路径 $(u,v)$ 的颜色计数可由树上差分表示：$root[u]+root[v]-root[lca]-root[fa[lca]]$，对应四个主席树节点。
• 询问两条路径时，得到两组四个根节点，递归比较颜色区间 $[1,n]$ 的哈希值是否相等。
• 若左半区间 $[l,mid]$ 的哈希值相等，说明该区间内所有颜色的计数完全相同，答案在右半区间；否则答案在左半区间。
• 递归至叶子节点 $l$，若哈希值相等则返回 $l+1$，否则返回 $l$。
• 最终输出返回值减一，即第一个计数不同的颜色编号减一；若全部相同则输出 $n$。
• 使用树链剖分求 $lca$，主席树动态开点，总复杂度 $O((n+Q)\log n)$。

T3 六元组

那T2都挂分且是很艰难才做出来的，T3肯定是做不出来了，时间也不够。

暴力呗，还能拿点分ovo

20pts

本题正解思路小总结：

• 由题意，训练计划构成一个长度为 $3$ 的环，可转化为在排序离散化后的飞机中，寻找满足区间传递覆盖的三元组 $(a, b, c)$。
• 先对飞机按初始位置 $x_i$ 排序并离散化，将降落区间 $[l_i, r_i]$ 转化为排序后的离散下标区间 $[l’_i, r’_i]$。
• 固定第一架飞机 $a$（枚举其初始位置 $x$），用事件扫描线动态将满足 $x \in [l’_b, r’_b]$ 的第二架飞机 $b$ 加入数据结构。
• 遍历 $a$ 能降落的机场 $y$（即 $y \in [l’_a, r’_a]$），累加满足 $y \in [l’_b, r’_b]$ 的飞机 $b$ 能提供的第三架飞机 $c$ 的数量，即区间包含 $x$ 的 $c$。
• 利用分块（根号分治）维护每个位置被多少架飞机 $c$ 的降落区间覆盖，散块暴力查询，整块利用预处理的 pre_cal 前缀和快速统计。
• 对于 $b$ 的降落区间，用 $O(1)$ 差分查询 qry(r'[j]) - qry(l'[j]-1) 得到能降回起点 $x$ 的飞机 $c$ 数量。
• 累加所有枚举得到的合法方案数，时间复杂度为 $O(m \sqrt{m})$。

T4 图

暂无