「Solution」拦截导弹

我爱调代码

$\mathcal{Link}$

link

$\mathcal{Sol}$

定义 $f_0(i)$ 为以 $i$ 为终点的最长上升子序列的长度， $g_0(i)$ 为 $f_0$ 的个数。
同样地，定义 $f_1(i)$ 为以 $i$ 为起点的最长上升子序列的长度， $g_1(i)$ 为 $f_1$ 的个数。
那么记方案总数为 $tot$ ，第二问的答案即是 $\frac{g_0(i) \times g_1(i)}{tot}$
暴力转是 $\mathcal{O}(n^2)$ 的。
因为是个三维的偏序，可以用 cdq 来优化。
代码要想清楚再写，注意细节，手不要乱抖。。。

$\mathcal{Code}$

#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 5e5 + 5;

int n, m, cnt, maxl, num[MAXN], f[MAXN][3];
double g[MAXN][3], tot;
struct Node { int h, v, t; } a[MAXN];
map<int, int> h;

// 线段树维护区间最大值以及最大值的个数
struct Result { int f; double g; };
struct SegmentTree { int l, r, dat; double sum; } s[MAXN << 2];
void push_up(int p) {
	s[p].dat = max(s[p << 1].dat, s[p << 1 | 1].dat), s[p].sum = 0;
	if (s[p << 1].dat == s[p].dat) s[p].sum += s[p << 1].sum;
	if (s[p << 1 | 1].dat == s[p].dat) s[p].sum += s[p << 1 | 1].sum;
}
void clear(int p) {
	if (s[p].dat == 0) return;
	s[p].dat = 0, clear(p << 1), clear(p << 1 | 1), push_up(p);
}
void build(int p, int l, int r) {
	s[p].l = l, s[p].r = r;
	if (l == r) { s[p].dat = 0, s[p].sum = 0; return; }
	int mid = (s[p].l + s[p].r) >> 1;
	build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
	push_up(p);
}
void update(int p, int x, int val, double num) {
	if (s[p].l == s[p].r) { 
		if (val == s[p].dat) s[p].sum += num;
		else if (val > s[p].dat) s[p].dat = val, s[p].sum = num;
		return;
	}
	int mid = (s[p].l + s[p].r) >> 1;
	if (x <= mid) update(p << 1, x, val, num);
	else update(p << 1 | 1, x, val, num);
	push_up(p);
}
Result query(int p, int l, int r) {
	if (s[p].l >= l && s[p].r <= r) { return Result{s[p].dat, s[p].sum}; }
	int mid = (s[p].l + s[p].r) >> 1; Result res = {0, 0}, tmp1 = {0, 0}, tmp2 = {0, 0};
	if (l <= mid) tmp1 = query(p << 1, l, r);
	if (r > mid) tmp2 = query(p << 1 | 1, l, r);
	res.f = max(tmp1.f, tmp2.f);
	res.g += (res.f == tmp1.f) * tmp1.g + (res.f == tmp2.f) * tmp2.g;
	return res;
}

void cdq(int l, int r, int opt) {
	if (l == r) return;
	int mid = (l + r) >> 1, pos = l;
	sort(a + l, a + r + 1, [](const Node& x, const Node& y) { return x.t < y.t; });

	cdq(l, mid, opt);  // 注意要算完左边的贡献后立即与右边合并，保证转移从左向右不中断
	sort(a + l, a + mid + 1, [](const Node& x, const Node& y) { return (x.h == y.h) ? x.t < y.t : x.h > y.h; });
	sort(a + mid + 1, a + r + 1, [](const Node& x, const Node& y) { return (x.h == y.h) ? x.t < y.t : x.h > y.h; });
	
	clear(1);

	for (int i = mid + 1; i <= r; i++) {
		while (pos <= mid && a[pos].h >= a[i].h) update(1, a[pos].v, f[a[pos].t][opt], g[a[pos].t][opt]), pos++; // 第一遍居然把 a[pos].v 写成了 a[pos].t 。。。
		Result res = query(1, a[i].v, n);
		if (!res.f) continue;
        // dp 转移最大值
		if (f[a[i].t][opt] == res.f + 1) g[a[i].t][opt] += res.g;
		else if (f[a[i].t][opt] < res.f + 1) f[a[i].t][opt] = res.f + 1, g[a[i].t][opt] = res.g;
		// printf("--%d %d\n", a[i].t, g[a[i].t][opt]);
	}

	cdq(mid + 1, r, opt); // 开始写掉了。。。

}

signed main() {

	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) scanf("%lld %lld", &a[i].h, &a[i].v), a[i].t = i, num[i] = a[i].v, m = max(m, a[i].h);
	sort(num + 1, num + 1 + n);
	for (int i = 1; i <= n; i++) if (num[i] != num[i - 1]) h[num[i]] = ++cnt;
	for (int i = 1; i <= n; i++) a[i].v = h[a[i].v], f[i][0] = f[i][1] = 1, g[i][0] = g[i][1] = 1.0;

	build(1, 1, n), cdq(1, n, 0);
	for (int i = 1; i <= n; i++) a[i].v = cnt - a[i].v + 1, a[i].h = m - a[i].h + 1, a[i].t = n - a[i].t + 1;
	sort(a + 1, a + 1 + n, [](const Node& x, const Node& y) { return x.t < y.t; });

	for (int i = 1; i <= n; i++) maxl = max(maxl, f[i][0]);
	printf("%lld\n", maxl);

	build(1, 1, n), cdq(1, n, 1);
	for (int i = 1; i <= n; i++) tot += (f[i][0] == maxl) * g[i][0];

	// for (int i = 1; i <= n; i++) {
	// 	printf("%d %d\n", g[i][0], g[i][1]);
	// }
	// printf("%d\n", tot);

	for (int i = 1; i <= n; i++) {
		if (f[i][0] + f[n - i + 1][1] - 1 != maxl) printf("0 ");
		else printf("%.6lf ", g[i][0] * (g[n - i + 1][1] / tot));
	}

	return 0;
}