【每日一题】Minimizing maximizer 题解

Description

The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer's inputs.

Maximizer is implemented as a pipeline of sorters Sorter(i1, j1), ... , Sorter(ik, jk). Each sorter has n inputs and n outputs. Sorter(i, j) sorts values on inputs i, i+1,... , j in non-decreasing order and lets the other inputs pass through unchanged. The n-th output of the last sorter is the output of the Maximizer.

An intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer would still produce the correct result. What is the length of the shortest subsequence of the given sequence of sorters in the pipeline still producing correct results for all possible combinations of input values?

Task
Write a program that:

reads a description of a Maximizer, i.e. the initial sequence of sorters in the pipeline,
computes the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible input data,
writes the result.

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

Solution

思路：dp + 线段树优化
首先很容易想到令 表示取第 个排序器时，最大值可以移动到第 个位置的最优方案。那么有状态转移方程 , 其中 表示在 里面的最小值，找到之后我们就能从该状态转移过来。
其中找最小值,单点更新这两步可以用线段树来完成，注意是poj的题目，头文件改一改。
总体时间复杂度

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
struct node {
  int l, r, minz;
}t[N << 2];
void push_up(int rt) {
  t[rt].minz = min(t[rt << 1].minz, t[rt << 1 | 1].minz);
}
void build(int rt, int l, int r) {
  t[rt].l = l, t[rt].r = r;
  if(l == r) {
    return ;
  }
  int mid = l + r >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  push_up(rt);
}
void update(int rt, int x, int val) {
  if(t[rt].l == t[rt].r) {
    t[rt].minz = min(t[rt].minz, val);
    return ;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(x <= mid) {
    update(rt << 1, x, val);
  } else {
    update(rt << 1 | 1, x, val);
  }
  push_up(rt);
}
int query(int rt, int ql, int qr) {
  if(t[rt].l >= ql && t[rt].r <= qr) {
    return t[rt].minz;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    return query(rt << 1, ql, qr);
  } else if(ql > mid) {
    return query(rt << 1 | 1, ql, qr);
  } else return min(query(rt << 1, ql, mid), query(rt << 1 | 1, mid + 1, qr));
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, m; cin >> n >> m;
  memset(t, 0x3f, sizeof(t));
  build(1, 1, n); // 建树
  update(1, 1, 0); // 把第一个点设置为0
  for(int i = 1; i <= m; i++) {
    int l, r; cin >> l >> r;
    int pos = query(1, l, r); // 找到前面的最小值
    update(1, r, pos + 1); // 状态转移
  }
  cout << query(1, n, n) << "\n"; // 输出
  return 0;
}