【解题报告】JOISC 2019 Day1

「JOISC 2019 Day1」考试

直接对 $(S_i,T_i,S_i+T_i)$ 三维数点就行了，$\text{CDQ}$ 分治 $\mathcal{O}(n\log^2 n)$。

需要注意一下，某一维相同的元素中，把点放在前面，询问放在后面才可以数 $\le$ 的情况。

「JOISC 2019 Day1」聚会

感觉和 CF1438F Olha and Igor 有点像啊。

考虑一条链要怎么问。

如果直接随机链上两个点 $x,y$，并询问所有其他点与这两个点之间的答案，那么在 $x,y$ 内部的点 $s$，会得到 $s$ 本身；不在 $x,y$ 内部的点会得到 $x$ 或者 $y$。这样就把集合划分为三块，递归求解即可。这个复杂度大概认为 $x,y$ 期望分布在序列的三等分点处，所以询问次数是：

$$ T(n)=3T(\dfrac{n}{3})+\mathcal{O}(n)=\mathcal{O}(n\log n) $$

再考虑放到树上，那还是随机两个点 $x,y$，询问其他所有点和 $x,y$ 的答案。对于 $x,y$ 这条路径上的点，会返回本身；对于 $x,y$ 路径上的点 $s$ 的子树内的点 $p$，也会返回 $s$；否则，返回 $x,y$ 中较近的一个。

这样就把集合划分为 $\mathcal{O}(\text{len})$ 个部分，其中 $\text{len}$ 是路径长度。实际上就是路径上每个点有一棵子树，外面有两个集合，而路径上的点还需要另外求解一次，这是因为还没有确定路径上点的顺序。

由于度数不大，所以大概可以认为在做一个类似边分治的过程？具体来说好像大家都不太会证，所以就鸽了。

「JOISC 2019 Day1」馕

有意思的题。

题目说要求每个人拿到的权值都不小于他拿到整个序列的权值的 $\dfrac{1}{n}$，那不妨考虑 虽然我想不到 把每一个人的 $n$ 等分点找出来。则现在对于每一个人，都有 $n-1$ 个断点，当某一个人占据的区间包含了自己划分出的某一个区间，则他就一定满意了。

考虑贪心。感觉上来说，每次选择要求最低的那一个人看起来很对。具体来说，使用这样的实现方法：

在选择第 $i$ 个断点的时候，在所有还没有分配区间的人的第 $i$ 个断点中，选择最靠左的一个，并将这个区间分配给这个人。

这为啥对呢？考虑第 $i$ 次被拎出来的人 $p$，他既然没有在第 $i-1$ 次被拎出来，说明他的第 $i-1$ 个端点，在被选的第 $i-1$ 个端点的右侧。而我现在又把 $p$ 给选出来了，所以我所占据的区间一定包含我的某一个等分区间。

因此对每个人都合法，没有无解情况。