LGP6146题解
思维僵化了，习惯按照右端点排序，没想到是按照左端点排序。。。
考虑从左到右依次加入线段，考虑贡献。
设前 \(i\) 条线段的答案为 \(dp[i]\)。
考虑两种情况：
-
不加，贡献为 \(dp[i-1]\)
-
加，首先贡献有 \(dp[i-1]\)，还有可能额外多出连通块。
考虑哪些集合会多出连通块。这些集合最右边的点明显不能超过第 \(i\) 条线段的左端点。只需要数出即可，做一个前缀和即可。
设这些线段有 \(x\) 条，多出的集合贡献是 \(2^x\)。
\[dp[i]=2\times dp[i-1]+2^x \]#include
#include
typedef unsigned ui;
const ui M=1e5+5,mod=1e9+7;
ui n,ans,pw2[M],S[M<<1];
struct line{
ui L,R;
inline bool operator<(const line&it)const{
return L