希望没人复制我的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
*/