Minimizing maximizer

题意

给你个区间

选出最少长度的序列,满足按序列顺序操作,每次对

的元素进行排序

最后在位置的数需要是最大的数(你必须保证对于任意的元素顺序,都满足这点)

分析

非常经典的题

很容易想到当最大的数在位置时如果都能满足条件,任意情况都能满足条件

于是定义表示当前覆盖了的最小区间个数

转移从里找最小值就好了

用线段树优化找最小值的过程即可

#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
const int maxn=5e6+10;
const int inf=1e9;
int n,m,dp[maxn],l[maxn],r[maxn],a[maxn],maxx[maxn];
void build(int rt,int l,int r)
{
    if( l==r ){ a[rt]=maxx[rt]=dp[l]; return; }
    build(lson); build(rson);
    maxx[rt] = min( maxx[ls],maxx[rs] );
}
void insert(int rt,int l,int r,int u)
{
    if( l==r&&l==u ){ a[rt]=maxx[rt]=dp[u]; return; }
    if( r<u||l>u )    return;
    insert(lson,u); insert(rson,u);
    maxx[rt] = min( maxx[ls],maxx[rs] );
}
int query(int rt,int l,int r,int L,int R)
{
    if( l>=L&&r<=R )    return maxx[rt];
    if( l>R||r<L )    return inf;
    return min( query(lson,L,R),query(rson,L,R) );
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
        scanf("%d%d",&l[i],&r[i]);
    dp[1]=0;
    for(int i=1;i<=n;i++)    dp[i]=inf;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        dp[r[i]] = min( dp[r[i]],query(1,1,n,l[i],r[i] )+1 );
        insert( 1,1,n,r[i] );
    }
    cout << dp[n];
}