专题题解 - NOI Online 2022 提高组

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$ 处的值计入答案，于是这就是一个二维偏序。

$m=4$ 时类似，枚举一行 $i$，对于某一个列二元组 $x,y$，再枚举不同于 $i$ 的两行 $j,k$，如果 $j,k$ 中一行大于 $i$ 而另一行小于 $i$ 就将 $j,k$ 在 $x,y$ 处的值计入答案，又是二维偏序，容易发现这样最大和最小的行分别算了 $3$ 次，中间两行分别算了 $1$ 次，所以减掉总和再除以 $2$ 即可。