Minimizing maximizer

做法：线段树优化dp

思路：

dp[i]表示覆盖[1,i]需要的最少区间数。然后用线段树更新取最小值。
dp[t]=min(dp[t],min(dp[s]~dp[t])+1)

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=5e4+10,INF=0x3f3f3f3f;

int n,m;
int dp[N<<2];

int query(int u,int l,int r,int x,int y){
    if(l>=x&&r<=y) return dp[u];
    int mid=(l+r)>>1,sum=INF;
    if(x<=mid) sum=query(u<<1,l,mid,x,y);
    if(y>=mid+1) sum=min(sum,query(u<<1|1,mid+1,r,x,y));
    return sum;
}

void modify(int u,int l,int r,int x,int y){
    if(l==r) dp[u]=min(dp[u],y);
    else{
        int mid=(l+r)>>1;
        if(x<=mid) modify(u<<1,l,mid,x,y); 
        else if(x>=mid+1) modify(u<<1|1,mid+1,r,x,y);

        dp[u]=min(dp[u<<1],dp[u<<1|1]);
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    memset(dp,INF,sizeof dp);
    cin>>n>>m;
    modify(1,1,n,1,0);
    for(int i=0;i<m;i++){
        int s,t;cin>>s>>t;
        int temp=query(1,1,n,s,t)+1;
        modify(1,1,n,t,temp);
    }
    cout<<query(1,1,n,n,n)<<"\n";
    return 0;
}