|
题目链接: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;
}


|