题面

题目描述

著名的植物学家 Alice 经过多年的探索，终于找到了传说中的璀璨花。璀璨花的生长速度非常迅猛，如果不加以合适的控制，璀璨花会因为过度内耗而死亡。璀璨花的生长趋势可以用序列 $a$ 表示，Alice 在研读前人对璀璨花的研究后总结出了一个控制序列 $b$ 。Alice 需要让璀璨花的生长趋势尽可能贴合控制序列，这样璀璨花就能尽可能快且安全地生长，以让更多人能欣赏到传说花卉的美。

Alice 可以通过基因编辑技术让 $a$ 的任意子序列 $a'$ 成为璀璨花的生长趋势，设 $a'$ 的长度为 $n$ ，若 $\forall i\in[1,n'-1]\cap\mathbb{N},a_{i+1}'>b_ia_i'$ ，那么璀璨花的培育趋势就是安全的。另外，越长的生长趋势能让成熟的璀璨花更美，所以 Alice 想知道可能的最长的璀璨花生长趋势子序列的长度。

Sample Input

4
1 2 3 10
2 3 4 5

Sample Output

3

数据范围

$N\leq10^6,1\leq a_i\leq10^{12},1\leq b_i\leq10^6$ 。

题解

加上一个条件的 LIS，考虑到状态太大，除非用动态开点线段树或者 map 树状数组，否则只能二分贪心。

代码

const int N = 1e6 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	ll a[N], b[N], f[N];

	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) a[i] = Read();
		for (int i = 1; i <= n; i++) b[i] = Read();
		int len, pos;
		f[len = pos = 1] = a[1];
		for (int i = 2; i <= n; i++) {
			if (a[i] > f[pos] * b[pos]) {
				f[++pos] = a[i];
				continue;
			}
			if (a[i] < f[1]) {
				f[1] = a[i];
				continue;
			}
			int p = -1, l = 0, r = pos;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (a[i] > f[mid] * b[mid]) p = mid, l = mid + 1;
				else r = mid - 1;
			}
			p++;
			if (p <= pos && a[i] < f[p]) f[p] = a[i];
		}
		printf ("%d\n", pos);
		return 0;
	}
}

int main () {
	freopen("alice.in", "r", stdin);
	freopen("alice.out", "w", stdout);
	Main::main();
	return 0;
}