最小覆盖(cover)、、线段树
【题目描述】
给定 N 个区间[Li,Ri]，需要你按照顺序选出一个区间序列使得[1,M]完全被覆盖。并且在选出来的序列中，某个区间[a,b]之前必须保证[1,a]都被已经选中的区间覆盖（即没有“断开”的地方）。求出最少需要选多少区间
【输入文件】
第一行两个整数 M 和 N。
以下 N 行每行两个正整数 Li,Ri 表示这个区间。
【输出文件】
一个整数，表示最少的区间数。
【样例输入】
40 6
20 30
1 10
10 20
20 30
15 25
30 40
【样例输出】
4
【样例解释】
[1,10]-[10,20]-[20,30]-[30,40]
【数据规模】
对于 100%的数据 1<=N<=500000， 0<=M<=50000
先不看数据，知道这是一道DP题。
F[i]表示填满1~i区间最少需要几个区间。
因为数据范围大，所以用线段树维护。
code：
#include <cstdio>
#include <cctype>
#include <algorithm>
#define C c = tc ( )
using namespace std;
inline char tc(){
static char fl[],*A,*B;
return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;
}
inline int read(){
char c;int x=,y=;
while(!isdigit(C)&&c!='-');c=='-'?y=-:x=c-'';
while(isdigit(C))x=x*+c-'';
return x*y;
}
struct node{
int x,y;
}a[];
int m,n,seg[*+],add[*+];
void up(int node){seg[node]=min(seg[node<<],seg[(node<<)+]);}
void down(int node){
if(add[node]!=){
add[node*]=min(add[node*],add[node]);
add[node*+]=min(add[node*+],add[node]);
seg[node*]=min(seg[node*],add[node]);
seg[node*+]=min(seg[node*+],add[node]);
add[node]=;
}
return ;
}
int query(int node,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r)return seg[node];
int mid=(l+r)>>;
down(node);
int ans=;
if(ql<=mid)ans=min(ans,query(node*,l,mid,ql,qr));
if(qr>mid) ans=min(ans,query(node*+,mid+,r,ql,qr));
return ans;
}
void change(int node,int l,int r,int cl,int cr,int v){
if(cl<=l&&cr>=r){
seg[node]=min(seg[node],v);
add[node]=min(add[node],v);
return ;
}
int mid=(l+r)>>;
down(node);
if(cl<=mid)change(node*,l,mid,cl,cr,v);
if(cr>mid) change(node*+,mid+,r,cl,cr,v);
up(node);
}
int main(){
freopen("cover.in","r",stdin);
freopen("cover.out","w",stdout);
m=read(),n=read();
for(int i=;i<=n;i++)a[i].x=read(),a[i].y=read();
for(int i=;i<=m*;i++)seg[i]=add[i]=;
change(,,m,,,);
for(int i=;i<=n;i++){
int p=query(,,m,a[i].x,a[i].y);
if(p==)continue;
change(,,m,a[i].x,a[i].y,p+);
}
printf("%d",query(,,m,m,m));
fclose(stdin),fclose(stdout);
return ;
}