题解：P11340 [COI 2019] TENIS

FstAutoMaton · 2025-10-27 20:57:47 · 题解

[COI 2019] TENIS

数据结构题。

考虑暴力，每次选择一个数和一个维度将所有那一维小于它的数对加入（即能战胜的集合），最终所有数都被选上就说明合法。时间复杂度根据实现方式为单次询问 \operatorname{O}(n\log n)\sim \operatorname{O}(n^2)。

考虑如何快速 check。将三场比赛中的选手按照名次从 1 到 n 排列，根据上面的 check 方案，可以注意到在这个表格中一定是一段前缀中出现过的选手才有可能夺冠。

假设这个前缀长度为 p ，对于每个人，设 l_i 表示其排名最靠前为多少，r_i 表示其排名最靠后为多少。如果出现了 l_i\le p<r_i 就说明 i 是可以被战胜的，p 就应该至少为 r_i。所以不存在 i 使得 l_i\le p<r_i。

直接做是 \operatorname{O}(nq) 的，考虑用数据结构维护上述条件。将第 l_i 个位置加上 1，第 r_i 个位置加上 -1，对其做前缀和，那么 p 就是第一个前缀和为 0 的地方。每次修改操作就是对后缀加上 1，查询操作就是查询第一个为 0 的位置。用在线段树上二分可以做到 \operatorname{O}(q\log n)。