Minimizing maximizer（线段树）

题目：

给一个长为的，落在上的区间序列，问最短的子序列，相邻区间有交集，连续覆盖上所有点。
。

做法：

线段树上每个叶子表示上的一个点，维护当前延伸到需要的最短区间序列长度。一开始设结点1为0，其他点为。每次读入一个区间，左端点，即用已有的区间延伸到所需的最短区间序列长度，设为。然后用，线段树上区间的值。最后终点的值即为答案。

代码：

#include <cstdio>
#include <algorithm>
#define lson rt<<1
#define rson rt<<1|1
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int inf = 0x3f3f3f3f;
int lazy[N<<2];
void build(int l, int r, int rt){
    lazy[rt] = inf;
    if (l == r){
        if (l == 1) lazy[rt] = 0;
        return;
    } 
    int mid = (l+r) >> 1;
    build(l, mid, lson);
    build(mid+1, r, rson); 
}
void pushdown(int rt){
    lazy[lson] = min(lazy[lson], lazy[rt]);
    lazy[rson] = min(lazy[rson], lazy[rt]);
    lazy[rt] = inf;
}
void update(int L, int R, int x, int l, int r, int rt){
    if (L <= l && r <= R){
        lazy[rt] = min(lazy[rt], x); return;
    }
    if (lazy[rt] != inf) pushdown(rt);
    int mid = (l+r) >> 1;
    if (L <= mid) update(L, R, x, l, mid, lson);
    if (R > mid) update(L, R, x, mid+1, r, rson);
}
int query(int pos, int l, int r, int rt){
    if (l == r) return lazy[rt];
    if (lazy[rt] != inf) pushdown(rt);
    int mid = (l+r) >> 1;
    if (pos <= mid) return query(pos, l, mid, lson);
    else return query(pos, mid+1, r, rson);
}
int main(void){
    int n, m; scanf("%d%d", &n, &m);
    build(1, n, 1);
    for (int i = 1; i <= m; ++i){
        int l, r; scanf("%d%d", &l, &r);
        int k = query(l, 1, n, 1);
        update(l, r, k+1, 1, n, 1);
    }
    printf("%d\n", query(n, 1, n, 1));
    return 0;
}