题解 P6146 【[USACO20FEB]Help Yourself G】

· · 题解

先将所有线段按左端点升序排序。

设 f_i 表示前 i 条线段的所有子集的复杂度之和。

如果我们新添加了一条线段，复杂度会怎样变化呢？

  1. 不选这条线段。

这种情况下，复杂度没有变化，不包含这条线段的子集的复杂度仍然为 f_i。

  1. 选这条线段。

复杂度分两部分：原来的复杂度（这部分不会因为新选一条线段而减少，因为线段已经按左端点排好顺序了）和新增加的复杂度（这条线段可能不与已有线段形成连通块）。

原来的复杂度仍然为 f_i，而选这条线段可能会让部分子集的复杂度 +1。

如果之前的线段中有 x 条线段不与当前线段相交，则选这 x 条线段的一个子集加上当前线段可以让复杂度在原来子集的复杂度基础上 +1。

根据集合的知识，新增加的复杂度就是 2^x。

从而得到递推式：f_i=f_{i-1}+(f_{i-1}+2^x)=2f_{i-1}+2^x。

现在的问题就是计算 x。

容易看出，设第 i 条线段的左端点为 l_i，右端点为 r_i，则 x 等于右端点小于 l_i 的线段数量。

我们可以利用前缀和技巧来预处理所有 x 的值。

#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
struct seg
{
 int l,r;
}a[100005];
int s[200005];
long long f[100005];
bool cmp(const seg&a,const seg&b)
{
 return a.l<b.l;
}
long long fpow(long long x,long long y)
{
 long long ans=1;
 while(y)
 {
  if(y&1)ans=ans*x%MOD;
  x=x*x%MOD;
  y>>=1;
 }
 return ans;
}
int main()
{
 int n;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i].l>>a[i].r;
  s[a[i].r]++;
 }
 sort(a+1,a+n+1,cmp);
 for(int i=1;i<=2*n;i++)
  s[i]+=s[i-1];
 for(int i=1;i<=n;i++)
  f[i]=(2*f[i-1]+fpow(2,s[a[i].l-1]))%MOD;
 cout<<f[n]<<endl;
 return 0;
}