14239: 【原4239】Price

题目描述

author: Galaxies 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4239

商品定价

题目描述

考拉开了一家商店，这家商店的货架是从左向右有次序的，货架上一共摆放了$n$个商品。
对于每一个商品，考拉规定了一个定价区间$[L_i,R_i]$，这个商品的价格只能在这个定价区间内选择一个正整数$p_i$作为该商品的标价，也就是说所有$p_i$满足$p_i \in \mathbb{N}, p_i \in [L_i, R_i]$。
顾客走进商店，从第1个商品依次看到第$n$个商品时，会有一个满意指数$w$。这个满意指数表示着顾客所看到的商品定价的最长上升子序列的长度。也就是说，如果现在已有一个商品价格序列${p_n}$，那么满意指数$w$就是最长下标序列$n_k$的长度$k$，满足$p_{n_i} > p_{n_{i-1}} (1 < i \leq k)$。
举一个简单的例子，1 3 2 4 5 的最长上升子序列为1 2 4 5 或 1 3 4 5，其长度为4。
考拉认为，顾客的满意指数$w$越高，他的利润就会越高，因此他想让你帮他合理定价，使得满意指数$w$最大，你只需要输出最大的满意指数$w$即可。

输入描述

第一行一个数$n$，表示商品总数。
接下来$n$行，每行两个数$L_i, R_i$，表示第$i$个商品的定价区间为$[L_i, R_i]$。

输出描述

仅一行，一个数$w$，表示最大的满意指数，含义如题目描述所示。

输入样例

5 3 3 4 8 5 5 2 4 3 9

输出样例

4

样例解释

其中一种方案定价序列为3, 4, 5, 4, 6，其最长上升子序列长度为4。

数据范围

本题目共有10个测试点，每个测试点通过得10分，测试点的具体数据范围如下：
对于第1~3个测试点，$1 \leq n \leq 10^3, L_i = R_i$；
对于第4~7个测试点，$1 \leq n \leq 10^3, 1 \leq L_i \leq R_i \leq 5 \times 10^4 $；
对于第8个测试点，$1 \leq n \leq 3 \times 10^5, L_i = R_i$
对于100%的数据，$1 \leq n \leq 3 \times 10^5, 1 \leq L_i \leq R_i \leq 2 \times 10^9$。

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int stack_data[300009] = { 0 };
int stack_n = 0;

int mid_search(int l, int r, int val) {
    if (val > stack_data[stack_n - 1])
        return stack_n;
    int right_ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (stack_data[mid] >= val) {
            right_ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return right_ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;

        int lpos = mid_search(0, stack_n - 1, l),
            rpos = mid_search(0, stack_n - 1, r);

        if (lpos == stack_n) {
            stack_data[stack_n++] = l;
        }
        else {
            if (rpos == stack_n)
                ++stack_n;
            for (; rpos > lpos; --rpos) {
                stack_data[rpos] = stack_data[rpos - 1] + 1;
            }
            stack_data[lpos] = l;
        }
    }

    cout << stack_n;

    return 0;
}