Minimizing maximizer(线段树优化dp 好题）

题意：N个排序器，每个可以把第l个数到第r个数这个区间里面的数从小到大排序，这些排序器按顺序运行，最后一个排序器运行完第n个数为第n小（最大数）。这些排序器去掉若干个也可以完成任务，问最少要留下几个，才能使留下的排序器依次运行使得对于任何输入最后一个排序器输出的最后一个数字为最大数。（题意看的一个犇犇的）

题解：
一看很像一个dp，但是一看n,m铁T啊，数据至少有一个O（m）是跑不掉的 那么我们只有优化N了，先看dp，我们可以定义 dp[i][j]前i个我们选择了j个的最小次数 min(dp[i-1][j],dp[i-1][k]+1),依次枚举，但是这样超时，所以我们就要换一个想法 ，如何在区间里面的操作，我们既然规定了必须是有序的选择，那么就会想到线段树的操作，我们每次可以找到每个区间的最小值，如1-10 1-30，我们可以在这个区间查询最小值，先初始化1这个节点=0，然后查询1-10，之后11这个点就会继承为1-10的下一个区间 ，更新，下一次遇到1-30，我们可以找到1-30这个区间的最小还是0，因为线段树会继承每个区间最小值，然后就是更新31这个点+1，首先初始化所有0x3f3f3f3f,然后再更新1这个点的初始值0.最后查询就可以了 很经典

https://blog.nowcoder.net/n/2d0978c2683a4117931544e66052e7be
犇犇博客

上一个DP代码

 scanf("%d%d",&n,&m);
  for(int i = 1;i <= m;i++) scanf("%d%d",&s[i],&t[i]);
  memset(f,0x3f,sizeof(f));f[0][1] = 0;
  for(int i = 1;i <= m;i++) {
      for(int j = 1;j <= n;j++) {
          f[i][j] = f[i-1][j];
          if(j == t[i]) {
              for(int k = s[i];k <= t[i];k++)
              f[i][j] = min(f[i][j],f[i-1][k] + 1);
          }
      }
  }
  cout << f[m][n] << endl;

来手线段树的代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
#define ull unsigned long long
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mse(a,b) memset(a,b,sizeof a)
const int mod=1e9+7;
const int maxx=1e6+10;
using namespace std;
const long double PI = 3.14159265358979323846;
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
inline int read()
{ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); } while (isdigit(ch)) { x=x*10+ch-48;  ch=getchar();  } return x*f;}
struct node{
      int l,r,val;
}tree[maxx];
void pushup(int rt)
{
      tree[rt].val=min(tree[rt<<1].val,tree[rt<<1|1].val);
}
void build(int rt,int l,int r)
{
      tree[rt].l=l; tree[rt].r=r;
      if(l==r) return ;
      int mid = l + r >> 1;
       build(rt<<1,l,mid);
       build(rt<<1|1,mid+1,r);
       pushup(rt);
}
void update(int rt,int l,int r,int val)
{
      int L=tree[rt].l;
      int R=tree[rt].r;

      if(L>=l&&R<=r)
      {
            tree[rt].val=min(tree[rt].val,val);
            return ;
      }
      int mid = L + R >> 1;
      if(l<=mid) update(rt<<1,l,r,val);
      if(r>mid)  update(rt<<1|1,l,r,val);
      pushup(rt);
}
int querry(int rt,int l,int r)
{
      int L = tree[rt].l;
      int R = tree[rt].r;  ///不符合区间的直接返回
        if(L>r||R<l)  return 0x3f3f3f3f;
      if(L>=l && R<=r)
      {
           return tree[rt].val;
      }
      int mid = L + R >> 1;
    //  if(r<=mid) return querry(rt<<1,l,r);
     // else if(l>mid) return querry(rt<<1|1,l,r);
     // else
       return min(querry(rt<<1,l,r),querry(rt<<1|1,l,r)); //直接爆搜

}
signed main(){
      fio
      int n,m;
      n=read(),m=read();
      mse(tree,0x3f3f3f3f);
      build(1,1,n);
      update(1,1,1,0);
      while(m--)
      {
            int l,r;
           l=read(),r=read();
            int pos = querry(1,l,r);
            update(1,r,r,pos+1);
      }
      cout<<querry(1,n,n);
    // system("pause"); 
      return 0;
}