GDKOI2021 TG Day2T2 island (以及一些线段覆盖最左端点的碎碎念)
题面描述
给出n个点，有向边((i, i+1) in E), ((i, a_i) in E)
(a_i)会动态修改，求对于一个点(x)能到达的编号最小端点。
转化
经过观察发现，其实就是求线段集合 ([a_i, i])中(x)通过两两相交的区间到达的左端点。
解法
正着想不好想，我们试图求出第一个不被线段覆盖的点。
发现在线段树上维护被覆盖次数即可。
总结
正难则反？
给出n个点，有向边((i, i+1) in E), ((i, a_i) in E)
(a_i)会动态修改，求对于一个点(x)能到达的编号最小端点。
经过观察发现，其实就是求线段集合 ([a_i, i])中(x)通过两两相交的区间到达的左端点。
正着想不好想，我们试图求出第一个不被线段覆盖的点。
发现在线段树上维护被覆盖次数即可。
正难则反？