Minimizing maximizer

题目大意

有一条长度为的线段，然后会按照顺序给你条线段（固定起点终点）
问，你按照顺序使用这条线段，最少要多少条才能把整条线段覆盖完
但是题目有一个条件，大概就是这条线段至少与之前的覆盖的线段有一个交点

分析

那么这样的话，就可以设计动态转移方程表示从开始覆盖到的最小代价
然后因为要求了一定与前面的线段有交点，所以方程如下：

注：表示的是枚举到的是第个线段，而并不是一个二维的
然后直接这样维护，它的时间复杂度是，然后观察到这个是查询的一个区间最小值
就是说这个东西大概可以用一个叫做线段树的数据结构来维护一下，这样下来，时间复杂度就变成了
但是需要注意的是，更新的时候，只需要更新右端点的值，其他地方的值其实是没有用的

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int ans[maxn << 2];

void update(int l, int r, int p, int val, int x = 1)
{
    if (l == r) {
        ans[x] = min(ans[x], val);
        return ;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) update(l, mid, p, val, x << 1);
    else update(mid + 1, r, p, val, x << 1 | 1);
    ans[x] = min(ans[x << 1], ans[x << 1 | 1]);
}

int query(int l, int r, int tl, int tr, int x = 1)
{
    if (l >= tl && r <= tr) return ans[x];
    int mid = (l + r) >> 1;
    int res(maxn);
    if (tl <= mid) res = min(res, query(l, mid, tl, tr, x << 1));
    if (tr > mid) res = min(res, query(mid + 1, r, tl, tr, x << 1 | 1));
    return res;
}

signed main()
{
    int n = __read(), m = __read();
    memset (ans, 0x3f, sizeof (ans));
    update(1, n, 1, 0);
    while (m--) {
        int s = __read(), t = __read();
        int upt = query(1, n, s, t);
        update(1, n, t, upt + 1);
    }
    printf ("%d\n", query(1, n, n, n));
}