n 个人, 第 i 个初始在数轴 xi 处, 以 vi 的速率向正方向逃离. 某一时刻, 正常人和病人处于同一位置, 则正常人被感染. 问 2^n 种初始感染情况中, 有多少种, 在足够长的时间后, 所有人都被感染, 模 10^9 + 7. (1 ≤ n ≤ 2*10^5, |xi| ≤ 10^9, 1 ≤ vi ≤ 10^9, xi,vi 两两不同) 考完之后一脸懵逼, 你们为什么都在说 "区间" ......区间在哪儿......?
感觉右边一位神犇的分析方法不错 - x-t 图象. (哈哈哈, 如果这是物理考试, 我已经被老杨罚画图100遍了)
红色是感染源 (0代). 先分析他对速率小于自己的人的影响: - 速率小于他, 并且在前方 (蓝色): 一定会被感染 (1代). - 速率小于他, 并且在后方 (黄色): 不会被直接感染. 先考虑2代. 他们被1代感染, 并且是像蓝色这样, 初始在感染源前方, 且速率小于黄色的1代. 接着, 我们发现, 不存在所谓的3代 - 他们会在更早的时候被0或1代感染.
对速率大于自己的人的影响类似.
那么, 一个传染源 (x, v) 能感染的所有人是这些: - 所有速率小于他且不小于 min { vi | xi > x } 的人 - 所有速率大于他且不大于 max { vi | xi < x } 的人
这就是区间啦~ 问题转化为: n条线段, 有多少种方案选取线段, 使它们的并覆盖整个区间?
我们也许会设计这样的 DP 状态: 把所有线段按右端点排序, f(i) = 用前 i 条线段将 [1,ri] 完全覆盖, 第 i 条线段必选, 的方案数. 然而...... 
幸运的是, 不会出现两个区间 [L,R],[l,r], 使得 L < l ≤ r < R. 因为, 把所有点按位置排序, 从左到右, 左右端点非严格递增. 如果 L < l, 那么必然有 R ≤ r.
但是仍然可能有两个区间共用左/右端点. 规定右端点相同时, 左端点小的排前面, 就可以解决问题了. 这样, 一旦中间断开, 就再无挽回的机会, 因此只有将 [1,ri] 完全覆盖的状态才可能有用.
之前根本没有考虑到上面说的问题......我没有用 sort 排序, 而是每个右端点一个 vector, 由于从左往右向里面扔元素, 恰好就以左端点为第二关键字了......
一道好题.