zqs`s blog

有朋自远方来，虽远必诛

题解 【P2487 [SDOI2011]拦截导弹】

发表于 分类于 ， Valine：

写起来和调起来都很恶心的 CDQ+dp。

$f1_i$ 表示以第 $i$ 个导弹结尾的最长 LIS 长度，$f2_i$ 表示以第 $i$ 个导弹开头的最长 LIS 长度，$g1_i$ 表示以第 $i$ 个导弹结尾的最长 LIS 方案数，$g2_i$ 同理。

以下我们只考虑 $f1,g1$，并用 $f$ 代替 $f1$，$g$ 代替 $g1$。

这个 $f$ 的限制是个三维偏序，直接 cdq 套树状数组优化 dp 就行了。名字莫名吓人

那 $g$ 呢？四位偏序？算完了 $f$ 再来算 $g$ 显然是行不通的，所以要在计算 $f$ 的时候顺带计算 $g$。

然后计算 $f2,g2$ 同理，把序列反过来，$h,v$ 取个反（例如都设为 $114514-h_i$)就行了。

然后算出了这个后第一问就解决了，第二问对于导弹 $i$，假设总方案数为 $tot$，它被拦截的概率显然是若 $f1_i+f2_i-1$ 不等于第一问的答案就是 $0$ 的概率，否则就是 $\frac{g1_i\cdot g2_i}{tot}$。

完了？完了。

但这样说过于笼统，说了等于没说，所以我们还是理一下具体的东西和实现细节：

对于 $f_i$ 的计算，第一维 $j<i$ 的限制天然满足，第二维 $h_i\le h_j$ 我们 cdq 分治削掉，第三维 $v_i\le v_j$ 树状数组维护。

由于树状数组查最大值只能查 $[1,x]$ 不能查 $[x,n]$，所以我们 cdq 时要把 $h$ 和 $v$ 取个反变成 $h_j\le h_i,v_j\le v_i$。

对于 $g_i$ 的计算，在树状数组维护最大值时，顺带维护以下有多少种方案可以得到这种最大值。$g$ 的转移也是一个 dp，所以和 $f$ 一起算其实很自然。

还有就是方案数要开 double，long long 会炸，总方案数 tot 也要开 double。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <algorithm>
#include <cstring>

inline int max(const int x, const int y) {return x > y ? x : y;}
inline int min(const int x, const int y) {return x < y ? x : y;}
int f1[50005], f2[50005], h[50005], v[50005], n;
double g1[50005], g2[50005];
struct Node {
	int x, y, z;
	inline bool operator < (const Node a) const {return x < a.x;}
} a[50005];
struct Initer {
	int v, id;
	inline bool operator < (const Initer a) {return v < a.v;}//离散化用的，不用管
} b[50005];
struct cmp {//functor排序比函数快得多
	inline bool operator () (const Node a, const Node b) const {return a.y < b.y;}
};
struct cmp2 {
	inline bool operator() (const Node a, const Node b) {return a.x > b.x;}
};
struct BIT {//树状数组我用了时间戳清空，不会的左转https://www.cnblogs.com/imakf/p/14071208.html
	int nowtime, c[50005], t[50005];
	double cnt[50005];//方案数开double
	void update(int x, int d, double d2) {//注意update有三个参，多出来的一个是方案数
		for (int i = x; i <= n; i += (i & ~i + 1))
			if (nowtime ^ t[i]) t[i] = nowtime, c[i] = d, cnt[i] = d2;
			else {
				if (c[i] < d) c[i] = d, cnt[i] = d2;
				else if (c[i] == d) cnt[i] += d2;
			}
	}
	inline std::pair<int, double> query(int x) {
		int sum = 0;
		double sum2 = 0;
		for (int i = x; i; i -= (i & ~i + 1))
			if (nowtime == t[i]) {
				if (sum < c[i]) sum = c[i], sum2 = cnt[i];//树状数组顺带维护
				else if (sum == c[i]) sum2 += cnt[i];
			}
		return std::make_pair(sum, sum2);//树状数组返回的是pair,first为LIS长度，second为方案数
	}
	inline void clear() {++ nowtime;}
} bitf;

void CDQ1(int l, int r) {
	if (l == r) return;
	int mid = l + r >> 1, i = l, j = mid + 1;
	CDQ1(l, mid);
	std::sort(a + l, a + mid + 1, cmp()), std::sort(a + mid + 1, a + r + 1, cmp());
	while (i <= mid && j <= r) {
		if (a[i].y <= a[j].y) bitf.update(a[i].z, f1[a[i].x], g1[a[i].x]), ++ i;
		else {
			std::pair<int, double> ans = bitf.query(a[j].z);
			if (ans.first + 1 > f1[a[j].x])
				f1[a[j].x] = ans.first + 1, g1[a[j].x] = ans.second;
			else if (ans.first + 1 == f1[a[j].x]) g1[a[j].x] += ans.second;
			++ j;
		}
	}
	while (j <= r)  {
		std::pair<int, double> ans = bitf.query(a[j].z);
		if (ans.first + 1 > f1[a[j].x])
			f1[a[j].x] = ans.first + 1, g1[a[j].x] = ans.second;
		else if (ans.first + 1 == f1[a[j].x]) g1[a[j].x] += ans.second;
		++ j;
	}
	std::sort(a + mid + 1, a + r + 1);//cdq完了过后原始下标是乱序的，所以要sort回去
	bitf.clear(), CDQ1(mid + 1, r);
}
void CDQ2(int l, int r) {//复制cdq1，把f1改为f2，把g1改为g2，连个大于小于的符号都不用改，调用前直接反转序列
	if (l == r) return;
	int mid = l + r >> 1, i = l, j = mid + 1;
	CDQ2(l, mid);
	std::sort(a + l, a + mid + 1, cmp()), std::sort(a + mid + 1, a + r + 1, cmp());
	while (i <= mid && j <= r) {
		if (a[i].y <= a[j].y) bitf.update(a[i].z, f2[a[i].x], g2[a[i].x]), ++ i;
		else {
			std::pair<int, double> ans = bitf.query(a[j].z);
			if (ans.first + 1 > f2[a[j].x])
				f2[a[j].x] = ans.first + 1, g2[a[j].x] = ans.second;
			else if (ans.first + 1 == f2[a[j].x]) g2[a[j].x] += ans.second;
			++ j;
		}
	}
	while (j <= r)  {
		std::pair<int, double> ans = bitf.query(a[j].z);
		if (ans.first + 1 > f2[a[j].x])
			f2[a[j].x] = ans.first + 1, g2[a[j].x] = ans.second;
		else if (ans.first + 1 == f2[a[j].x]) g2[a[j].x] += ans.second;
		++ j;
	}
	std::sort(a + mid + 1, a + r + 1, cmp2());
	bitf.clear(), CDQ2(mid + 1, r);
}

void init(int *a, int &mx) {
	for (int i = 1; i <= n; ++ i) b[i].id = i, b[i].v = a[i];
	std::sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; ++ i)
		a[b[i].id] = a[b[i - 1].id] + 1 - (b[i].v == b[i - 1].v);
	mx = a[b[n].id] + 1;
	for (int i = 1; i <= n; ++ i) a[i] = mx - a[i];//众所周知树状数组只能求前缀max，取个反转化一下把后缀改为前缀
}

int main() {
	int mxh, mxv;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i)
		scanf("%d%d", h + i, v + i), f1[i] = g1[i] = f2[i] = g2[i] = 1;
	init(h, mxh), init(v, mxv);
	for (int i = 1; i <= n; ++ i) a[i].x = i, a[i].y = h[i], a[i].z = v[i];
	CDQ1(1, n);
	int ans = 0;
	double sum = 0;
	for (int i = 1; i <= n; ++ i) ans = max(ans, f1[i]);
	for (int i = 1; i <= n; ++ i)
		if (f1[i] == ans) sum += g1[i];//sum即为tot
	printf("%d\n", ans);
	std::sort(a + 1, a + n + 1);
	std::reverse(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++ i) a[i].y = mxh - a[i].y, a[i].z = mxv - a[i].z;//取反回来再cdq2
	CDQ2(1, n);
	for (int i = 1; i <= n; ++ i)
		if (f1[i] + f2[i] - 1 == ans) printf("%.5lf ", g1[i] * g2[i] / sum);
		else printf("0.00000 ");
	return 0;
}
-------------本文结束感谢您的阅读-------------