建模 将问题看成数轴上的nnn个点，左侧的点可以到达右侧任意点。现在共有333种操作： 111.增加一条xxx点到yyy点的有向边。 222.减少一条xxx点到yyy点的有向边。 333.查询xxx点可以到达的点的个数。 思考 由于x≤yx \leq yx≤y时不会有任何影响（默认左侧点可以到达右侧点），因此下面全部考虑x>yx>yx>y的情况 111.什么情况下xxx的可达点会增大？ 若xxx能够到达前面的点yyy，那么yyy右侧的所有点可达，此时可达点增加[y,x−1][y,x-1][y,x−1]内的所有点 222.增加一条xxx点到yyy点的有向边会发生什么？ [y,x][y,x][y,x] 内的所有点相互可达。eg：从任意点到达xxx，再从xxx到达yyy，再从yyy到达[y,x][y,x][y,x]内的任意点。 333.如何表示相互可达？ 设计一个数组visvisvis，初始化成000。当[y,x][y,x][y,x]相互可达时，visy∼visxvis_y \sim vis_xvisy ∼visx 全部非0。, 444.对于操作1、21、21、2，会发生什么？ 由第三点知，需要将visy∼visxvis_y \sim vis_xvisy ∼visx 全部+1+1+1表示可达。反之将visy∼visxvis_y \sim vis_xvisy ∼visx 整体−1-1−1。 555.如何求答案？ 我们需要找到：从xxx出发，能够到达的最左侧的点。由第三点知：若xxx可达yyy，则visy∼visxvis_y \sim vis_xvisy ∼visx 全部非0。因此我需要找到最小的yyy满足以上条件。考虑二分去找，同时我需要知道[y,x][y,x][y,x]范围内，visvisvis数组的最小值，若最小值为0则代表不可达，反之可达。 至此，我需要有一个数据结构满足区间修，区间最值，线段树显然非常合适。同时此题还考察了线段树上二分。时间复杂度O(nlogn)O(nlogn)O(nlogn)。tips:tips:tips:如果在线段树外面写二分，时间复杂度O(nlognlogn)O(nlognlogn)O(nlognlogn)，卡一下常可以拿到380380380分。 代码 提交记录里有很多好的写法，补药穴窝