标签：线段树，DP
题目
1.1 Description 送你在数轴上的 n 个区间和 m 个关键点, 你可以决定每个区间选或不选, 问有多少种方案覆盖 所有的关键点. 对 1000000009 取模. 1.2 Input Format 第一行两个整数 n,m, 分别表示区间个数和关键点个数. 接下来 n 行, 每行两个整数 li,ri, 表示一个区间 [li,ri]. 接下来 m 行, 每行一个整数, 第 i 行表示表示第 i 个关键点 xi. 1.3 Output Format 输出一行一个整数, 表示答案. 1.4 Sample 1.4.1 Input 4 4 3 8 1 6 3 8 2 7 8 4 6 3 1.4.2 Output 12 1.5 Constraints 对于前 20% 的数据, n,m ≤ 20; 对于前 40% 的数据, n,m ≤ 104; 对于另 10% 的数据, n ≤ 104,xi ≤ 104; 对于 100% 的数据, 1 ≤ n,m ≤ 500000,1 ≤ xi ≤ 109,1 ≤ li ≤ ri ≤ 109.
分析
首先对区间离散化, 再按左端点从小到大排序, 若左端点相同, 则按右端点从大到小排序. 考虑计算 dp(i) 表示前 i 个关键点都完全覆盖的方案. 对于一个区间 [l,r], 它可以将 dp(l−1)…dp(r−1) 转移到 dp(r) 上; 还可以将 dp(r)…dp(m) 通 通乘上一个 2. 用线段树维护即可.
线段树常数会比较大，这题好像有点卡常，或者可以写zkw线段树（但是区间乘法很难写）
我写的是普通的线段树版本
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define reg(x) for(edge *j=last[i];j;j=j->next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=5e5+6,mod=1e9+9;
int n,m,l[maxn],r[maxn],z[maxn],y[maxn],len,mx=0;
struct edge{int r;edge *next;}*last[maxn];
void insert(int u,int v){edge *p=new edge;p->r=v;p->next=last[u];last[u]=p;}
struct tree{
ll sum,mul;tree *ls,*rs;
tree(){sum=0;mul=1;}
void update(){sum=(ls->sum+rs->sum)%mod;}
void pushdown(){if(mul!=1)ls->sum=1LL*ls->sum*mul%mod,rs->sum=1LL*rs->sum*mul%mod,ls->mul=1LL*(ls->mul)*mul%mod,rs->mul=1LL*(rs->mul)*mul%mod,mul=1;}
void build(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
(ls=new tree)->build(l,mid);(rs=new tree)->build(mid+1,r);
}
void add(int pl,ll d,int l,int r){
if(l==r){sum=(sum+d)%mod;return;}
pushdown();
int mid=(l+r)>>1;
if(pl<=mid)ls->add(pl,d,l,mid);else rs->add(pl,d,mid+1,r);
update();
}
void rmul(int lx,int rx,ll d,int l,int r){
if(lx>rx)return;
if(l==lx&&r==rx){sum=1LL*sum*d%mod;mul=1LL*mul*d%mod;return;}
pushdown();
int mid=(l+r)>>1;
if(rx<=mid)ls->rmul(lx,rx,d,l,mid);else if(lx>mid)rs->rmul(lx,rx,d,mid+1,r);else ls->rmul(lx,mid,d,l,mid),rs->rmul(mid+1,rx,d,mid+1,r);
update();
}
ll querysum(int lx,int rx,int l,int r){
if(l==lx&&r==rx) return sum;
pushdown();
int mid=(l+r)>>1;
if(rx<=mid) return ls->querysum(lx,rx,l,mid);else if(lx>mid) return rs->querysum(lx,rx,mid+1,r);else return (ls->querysum(lx,mid,l,mid)+rs->querysum(mid+1,rx,mid+1,r))%mod;
}
}*t;
int main()
{
n=read();m=read();
rep(i,1,n)l[i]=read(),r[i]=read();
rep(i,1,m)y[i]=read(),z[i]=y[i];
sort(z+1,z+m+1);len=unique(z+1,z+m+1)-z-1;//去重
rep(i,1,m)y[i]=lower_bound(z+1,z+len+1,y[i])-z,mx=max(mx,y[i]);
rep(i,1,n)l[i]=lower_bound(z+1,z+len+1,l[i])-z,r[i]=upper_bound(z+1,z+len+1,r[i])-z-1,insert(l[i],r[i]); //离散化
(t=new tree)->build(0,len);t->add(0,1,0,len);
rep(i,1,len)
reg(i){
t->add(j->r,t->querysum(i-1,j->r,0,len),0,len);
t->rmul(j->r+1,len,2ll,0,len);
}
cout<<t->querysum(mx,len,0,len)<<endl;
return 0;
}
