|
|
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1451
  /**//*
 题意：
有这样一个机器Maximizer，它的输入是N(N <= 50000)个1到N的数，输出最
大的数。这个机器的工作原理是通过读入M(M <= 500000)对整数对(i, j)，然后
将下标为i到j的数字非递减排序，每次都有一个输出，最后一个整数对的输出就
是最大的那个数。
现在要求选出最小的整数对序列，使得先前的N个数的任意排列被处理后都能
得到正确的解。
解法：
线段树
思路：
题目读了好久，一直不明白意思，仔细研究了一下sample，原来就是找到一
些零碎的片段[a, b]，使得他们的并是全集[1, N]，并且这样的片段越少越好，
乍看之下以为是贪心，直接将片段按起点排序，然后贪心，但仔细读题发现，要
求求的是原序列的子序列，换言之，就是求出的序列的下标必须是递增的，所以
问题就转变为了求以下方程 dp[r[i]] = 1 + Min(dp[l[i]] dp[r[i]])。这里
的l[]和r[]表示片段的左右区间端点，即用[l[i], r[i]]表示第i个片段，dp[r[i]]
则表示能过通过之前的i块片段拼出[1, r[i]]的最小片段数目，是一个动态规划，
但是由于N很大，直接采用动态规划的话复杂度是O(N^2)的。
于是将问题转变一下，我们注意到状态转移的时候要求求l[i]到r[i]的最小值
，而且区间范围比较大，很容易想到用线段树来求区间最值，这样一来，问题就简
单许多了，每次询问区间的最大值，然后把最大值插入到当前片段的右端点所在的
区间内，询问和插入都有线段树来控制，复杂度O(logn)。
 */
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define maxn 500010
#define inf 10000000
struct Tree {
int son[2];
int Min;
  void clear() {
son[0] = son[1] = -1;
Min = inf;
 }
}T[maxn/4];
int tot;
int MMin(int a, int b) {
return a < b ? a : b;
}
void Query(int root, int l, int r, int a, int b, int& Min) {
if(l > b || r < a || root == -1 || T[root].Min >= Min)
return ;
if(l <= a && b <= r) {
Min = MMin(Min, T[root].Min);
return ;
}
int mid = (a + b) >> 1;
Query(T[root].son[0], l, r, a, mid, Min);
Query(T[root].son[1], l, r, mid+1, b, Min);
}
void Insert(int& root, int pos, int a, int b, int val) {
if(root == -1) {
root = tot++;
T[root].clear();
}
T[root].Min = MMin(T[root].Min, val);
if(a == pos && pos == b) {
return ;
}
int mid = (a + b) >> 1;
if(pos <= mid)
Insert(T[root].son[0], pos, a, mid, val);
else
Insert(T[root].son[1], pos, mid+1, b, val);
}
struct Interval {
int l, r;
}Intv[maxn];
int n, m;
int hash[maxn], Case;
int tId = 0, rehash[maxn];
// 离散化
void Discreate() {
int i;
tId = 0;
for(i = 1; i <= n; i++) {
if(hash[i] == Case) {
rehash[i] = ++ tId;
}
}
for(i = 0; i < m; i++) {
Intv[i].l = rehash[ Intv[i].l ];
Intv[i].r = rehash[ Intv[i].r ];
}
}
int main() {
int i, j;
while(scanf("%d %d", &n, &m) != EOF) {
Case ++;
for(i = 0; i < m; i++) {
scanf("%d %d", &Intv[i].l, &Intv[i].r);
hash[Intv[i].l] = Case;
hash[Intv[i].r] = Case;
}
Discreate();
tot = 0;
int root = -1;
Insert(root, 1, 1, tId, 0);
for(i = 0; i < m; i++) {
int MM = inf;
Query(root, Intv[i].l, Intv[i].r, 1, tId, MM);
if(MM != inf) {
Insert(root, Intv[i].r, 1, tId, MM + 1);
}
}
int MM = inf;
Query(root, tId, tId, 1, tId, MM);
if(MM == inf)
MM = m;
printf("%d\n", MM);
}
return 0;
}
|