Minimizing maximizer

写在前面的话

蒟蒻流下了不学无术的眼泪，英语不好是真的硬伤，蒟蒻在巨佬的提示下才勉强明白了题意

题意

你有条按顺序（很重要！）给出的线段，要求你使用最少的线段覆盖。另外在你选择一条线段时你必须保证你的前置线段已全部被覆盖。

思路

我们可以定义为前个排序器将第个数提到所需要的最少的排序器的数量，那么当的时候 当的时候 ,我们状态数有个，显然是会飞的结果啊。所以考虑使用线段树来优化一下就好。

代码

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <map> 
#include <queue> 
#include <set>
#include <stack>
#include <string>
#include <typeinfo>
#include <vector>
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
const int N=1e5+5,INF=0x3f3f3f3f;
using namespace std;

int n,m;
struct segment
{
    int l,r,x;
}seg[N<<2];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

void build(int rt,int l,int r)
{
    seg[rt].l=l;seg[rt].r=r;
    if(l == r) 
    {
        int val=INF;
        if(l == 1) val=0;
        seg[rt].x=val;
        return ;
    }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    seg[rt].x=min(seg[lson].x,seg[rson].x);
}

int query(int rt, int l, int r) 
{
    if(seg[rt].l==l&&seg[rt].r==r) 
        return seg[rt].x;
    int mid=(seg[rt].l+seg[rt].r)/2;
    if(r<=mid)
        return query(lson,l,r);
    else if(l>mid)
        return query(rson,l,r);
    else
    {
        int v1=query(lson,l,mid);
        int v2=query(rson,mid+1,r);
        return min(v1,v2);
    }
}

void update(int rt, int i, int c) 
{
    if(seg[rt].l==seg[rt].r&&seg[rt].l==i) 
    {
        seg[rt].x=c;
        return ;
    }
    int mid=(seg[rt].l+seg[rt].r)/2;
    if(i<=mid)
        update(lson,i,c);
    else
        update(rson,i,c);
    seg[rt].x=min(seg[lson].x,seg[rson].x);
}

int main()
{
    n=read();m=read();
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int s,t;
        s=read();t=read();
        int v=min(query(1,s,t)+1,query(1,t,t));
        update(1,t,v);
    }
    printf("%d",query(1,n,n));
    return 0;
}

写在后面的话

为什么不支持万能头这么好的东西 TAT