|
|
題目鏈接：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;
}
|