NOI Online

· · 个人记录

NOI Online 场外人胡编乱造

T1：

Key Observation：区间 [l_i,r_i] 中的某个 x 对答案有贡献，当且仅当从 1 到 n 依次将每个二元组加入单调栈时，加入 x 时 x 之下没有元素或 x 之下的元素编号小于 l_i。

于是可以主席树/离线树状数组。

T2：

对每个题 i 维护一个会做它的人 t_i，初始为 0。

按照会做的题数从大到小考虑每个人，加入一个人时看看他会的所有题是否有相同的 t_i，如果是则将这些 t_i 都赋值为这个人，否则可以找一个其中的不为 0 的 t_i 就与当前的人构成答案（好像要找其中会做题数最少的人）。

T3：

首先可以假设最小值和最大值都唯一（比如如果两行一样，定义行数小的那个更小）。

考虑 m=3，总共只有三行，我们枚举一行 i，对于某一个列二元组 x,y，则当且仅当剩下两行中一行大于 i，一行小于 i，才会将剩下两行在 x,y 处的值计入答案，于是这就是一个二维偏序。