E. Boring Segments （双指针 + 线段树）

题意：给出n条线段的左右端点和权值$l_i$，$r_i$，$w_i$。要求选择一些线段，使得能够从数轴上的1出发，沿着线段走，能够到达m（连通，不是覆盖）。问选择的线段中最大权值与最小权值的差的最小值是多少。$1≤n≤3⋅10^{5}$，$2≤m≤10^{6}$.

思路：

　　我们最终选择的线段中一定有一个权值最大的线段，相应的也一定有权值最小的线段，这两个极值的差将构成最终的答案，权值位于二者之中的线段对答案没有影响，所以我们可以都选上。有了这个考虑，思路就可以转换成枚举答案中权值最大最小的线段。

　　先将线段根据$w_i$从小到大排序，然后从左向右枚举线段R（权值最大的线段），考虑：线段R作为最大权值时，最左侧的L（权值最小的线段）最大能是多少，满足将区间1~m连通。通过分析我们得知，当R不断向右移动时，L要么不变，要么向右走直到找到最大值，总之不会回退，因此这个过程可以用双指针维护。

　　至于如何判断线段[L,R]能将区间1~m连通，我们需要用线段树来维护。线段树里需要维护的信息有：该区间被添加了几次的计数变量add,同时还要有判断左右两个区间是否都被连通了的变量minn。在初始化和添加删除边的过程中add和minn维护的值并无差别，只是在回溯的时候minn = min(t[ls].minn, t[rs].minn)，如果minn大于1，则说明左右两个子区间都被连通了，否则说明没有连通。所以想要判断1~m有没有连通，只需要看t[1].minn是否大于0即可。

　　还有一个细节，因为我们要判断1~m是否连通而不是覆盖，所以我们需要把边转换为点，将点理解成点i延伸向i+1的线段即可，所以m--，每个线段的右端点ri--，就可以判断了。

代码：https://codeforces.com/contest/1555/submission/194738911