std

Star 2022-08-12 15:38:40 2022-08-12 15:41:57

希望没人复制我的std

正解是线段树或者树状数组

// Title : 钟离移山
// Date : 2022/8/12
// Author : Star
#include <cstdio>
#include <unordered_map>
#include <set>

using namespace std;

const int N = 200010; // 卡掉O(n^2)

// 树状数组
struct Node
{
    int a[N], b[N]; // a储存最大值, b储存最大值的下标
    int n;

    void add(int x, int v, int t) {
        for (int i = x; i <= n; i += i & -i) {
            if (v > a[i]) {
                b[i] = t;  // 后来的只有更优才能替换,否则字典序不是最小 
                a[i] = v;
            }
        }
    }

    int query(int x) { // 输出最大值
        int t = 0;
        for (int i = x; i; i -= i & -i) {
            t = t > a[i] ? t : a[i];
        }
        return t;
    }

    int qpos(int x) { // 输出最大值所在的编号
        int t = 0, p = 0;
        for (int i = x; i; i -= i & -i) {
            if (t < a[i]) { // 不要取等,否则不能保证字典序
                t = a[i];
                p = b[i];
            }
        }
        return p;
    }
    
} tr;

set<double> s; // 离散化使用
unordered_map<double, int> mp; // 离散化映射
double a[N]; // 储存斜率
int pre[N]; // lis输出方案的前驱数组

void print(int x) { // 递归输出答案
    if (pre[x]) print(pre[x]);
    printf("%d ", x);
}

void lisanhua() { // 离散化
    int i = 0;
    for (auto it : s) {
        mp[it] = ++i; // 建立映射
    }
}

int main() {
    int n, mx = 0; // mx记录离散化后最大的数是多少(与set的size相等)
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int h, d;
        scanf("%d%d", &h, &d);
        a[i] = (double)h / d; 
        s.insert(a[i]);
    }
    lisanhua();
    mx = s.size();
    tr.n = mx;
    for (int i = 1; i <= n; ++i) {
        // 更新前驱
        pre[i] = tr.qpos(mp[a[i]] - 1);
        // 加入当前节点和当前节点为尾的lis最长长度
        tr.add(mp[a[i]], tr.query(mp[a[i]] - 1) + 1, i);
    }
    // 输出答案
    printf("%d\n", tr.query(mx));
    print(tr.qpos(mx));
    printf("\n");
    return 0;
}

/*
sample input 
7
1 1
4 2
3 3
8 4
20 5
18 6
35 7

sample output
4
1 2 5 7
*/