|
|
題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1451
  /**//*
 題意：
有這樣一個(gè)機(jī)器Maximizer，它的輸入是N(N <= 50000)個(gè)1到N的數(shù)，輸出最
大的數(shù)。這個(gè)機(jī)器的工作原理是通過(guò)讀入M(M <= 500000)對(duì)整數(shù)對(duì)(i, j)，然后
將下標(biāo)為i到j(luò)的數(shù)字非遞減排序，每次都有一個(gè)輸出，最后一個(gè)整數(shù)對(duì)的輸出就
是最大的那個(gè)數(shù)。
現(xiàn)在要求選出最小的整數(shù)對(duì)序列，使得先前的N個(gè)數(shù)的任意排列被處理后都能
得到正確的解。
解法：
線段樹(shù)
思路：
題目讀了好久，一直不明白意思，仔細(xì)研究了一下sample，原來(lái)就是找到一
些零碎的片段[a, b]，使得他們的并是全集[1, N]，并且這樣的片段越少越好，
乍看之下以為是貪心，直接將片段按起點(diǎn)排序，然后貪心，但仔細(xì)讀題發(fā)現(xiàn)，要
求求的是原序列的子序列，換言之，就是求出的序列的下標(biāo)必須是遞增的，所以
問(wèn)題就轉(zhuǎn)變?yōu)榱饲笠韵路匠?nbsp;dp[r[i]] = 1 + Min(dp[l[i]] dp[r[i]])。這里
的l[]和r[]表示片段的左右區(qū)間端點(diǎn)，即用[l[i], r[i]]表示第i個(gè)片段，dp[r[i]]
則表示能過(guò)通過(guò)之前的i塊片段拼出[1, r[i]]的最小片段數(shù)目，是一個(gè)動(dòng)態(tài)規(guī)劃，
但是由于N很大，直接采用動(dòng)態(tài)規(guī)劃的話復(fù)雜度是O(N^2)的。
于是將問(wèn)題轉(zhuǎn)變一下，我們注意到狀態(tài)轉(zhuǎn)移的時(shí)候要求求l[i]到r[i]的最小值
，而且區(qū)間范圍比較大，很容易想到用線段樹(shù)來(lái)求區(qū)間最值，這樣一來(lái)，問(wèn)題就簡(jiǎn)
單許多了，每次詢問(wèn)區(qū)間的最大值，然后把最大值插入到當(dāng)前片段的右端點(diǎn)所在的
區(qū)間內(nèi)，詢問(wèn)和插入都有線段樹(shù)來(lái)控制，復(fù)雜度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;
}
|