Luogu2487 [SDOI2011]拦截导弹

博主： tony102
发布时间：2021 年 03 月 23 日
1878 次浏览
暂无评论
974字数
分类：题解

[Link](https://www.luogu.com.cn/problem/P2487)

这道题不要去darkbzoj上交，估计是当时没加SPJ导致你无论如何都过不去

## Sol

导弹拦截大家都会

现在已经给你了导弹来的顺序，我们把这个顺序记做 $t_i$

我们先来解决第一问，也就是最多能拦截的导弹数量。我们设 $f_i$ 表示以 $i$ 为最后一枚拦截的导弹前面最多能拦多少枚，记 $g_i$ 为达到 $f_i$ 的方案数。那么 $O(n^2)$ 的转移非常好写。在 $f_i$ 转移的时候看一下答案更新的情况，如果 $f_i$ 不变就乘法原理乘一下 $g_i$ ， 否则变成 $0$

注意到 $f_i$ 只能是从 $i$ 的左边转移过来，看看能不能用 cdq 分治解决这个问题。现在 $t_i$ 已经被确定，也就是说，已经有一维被确定，把 $h_i$ 当做第二维，每次 cdq 的时候查一查左边的$h$比右边的 $h$ 大的时候，就会产生贡献。更加具体的，我们把 $f_i$ 和 $g_i$ 插到线段树中，当要更新答案的时候就可以从线段树中取出最大的 $f_i$ 和 $g_i$ 更新当前的结果。

就这么写还是有锅，因为一种方案的方案数应该是以它开头和以它结尾的方案数的成绩。所以我们把三维全部逆过来，然后再做一遍 cdq 就可以了。

此外，注意方案数相加相乘会爆`long long`，用`double`存就可以了

## Code
```cpp
#include <bits/stdc++.h>
#define int long long
// #define double long double
using namespace std;

const int SIZE = 5e4 + 5;

int n;
int f1[SIZE], f2[SIZE];
double g1[SIZE], g2[SIZE], cpy[SIZE];

struct DF {	
	int t, h; double v;
} a[SIZE];

struct node {
	int l, r, mx; double cnt;
} tree[SIZE << 2];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using GTR::read;

#define lson(p) (p << 1)
#define rson(p) (p << 1 | 1)

void pushUp(int p) {
	tree[p].mx = std::max(tree[lson(p)].mx, tree[rson(p)].mx), tree[p].cnt = 0.00;
	if (tree[p].mx == tree[lson(p)].mx) tree[p].cnt += tree[lson(p)].cnt;
	if (tree[p].mx == tree[rson(p)].mx) tree[p].cnt += tree[rson(p)].cnt;
}

void build(int p, int l, int r) {
	tree[p].l = l, tree[p].r = r, tree[p].cnt = 0.00;
	if (l == r) {
		// tree[p].mx = f1[l], tree[p].cnt = g1[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(lson(p), l, mid); build(rson(p), mid + 1, r);
	pushUp(p);
}

void modify(int p, int pos, int f, double g) {
	if (tree[p].l == tree[p].r) {
		// std::cout << f << " " << tree[p].mx << endl;
		if (tree[p].mx < f) tree[p].mx = f, tree[p].cnt = 0.00;
		if (tree[p].mx == f) tree[p].cnt += g;
		// std::cout << p << " " << tree[p].mx << " " << tree[p].cnt << endl; 
		return;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (pos <= mid) modify(lson(p), pos, f, g);
	else modify(rson(p), pos, f, g);
	pushUp(p);
}

pair < int, double > query(int p, int l, int r) {
	if (l <= tree[p].l && tree[p].r <= r) {
		pair < int, double > ans;
		ans.first = tree[p].mx, ans.second = tree[p].cnt;
		// printf("%lld %lf\n", ans.first, ans.second);
		return ans;
	}
	int mid = (tree[p].l + tree[p].r) >> 1; pair < int, double > ansl, ansr, ans;
	if (l <= mid) ansl = query(lson(p), l, r);
	if (r > mid) ansr = query(rson(p), l, r);
	int mX = std::max(ansl.first, ansr.first); ans.first = mX, ans.second = 0.00;
	if (mX == ansl.first && l <= mid) ans.second += ansl.second;
	if (mX == ansr.first && r > mid) ans.second += ansr.second;
	return ans;
}

void clear(int p, int l, int r) {
	if (tree[p].mx == 0) return;
	tree[p].mx = 0;
	if (l == r) return;
	int mid = (l + r) >> 1;
	clear(lson(p), l, mid), clear(rson(p), mid + 1, r); 
}

int cmp1(DF a, DF b) { return a.t < b.t; }
int cmp2(DF a, DF b) { return a.h == b.h ? a.t < b.t : a.h > b.h; }

void cdq1(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	std::sort(a + l, a + r + 1, cmp1);; cdq1(l, mid);
	std::sort(a + l, a + mid + 1, cmp2); std::sort(a + mid + 1, a + r + 1, cmp2);
	clear(1, 1, n); pair < int, double > ans;
	for (int i = l, j = mid + 1; j <= r; ++ j) {
		while (i <= mid && a[i].h >= a[j].h) {
			modify(1, a[i].v, f1[a[i].t], g1[a[i].t]);
			++ i;
		}
		ans = query(1, a[j].v, n);
		if (ans.first == 0) continue;
		if (f1[a[j].t] < ans.first + 1) f1[a[j].t] = ans.first + 1, g1[a[j].t] = 0.00;
		if (f1[a[j].t] == ans.first + 1) g1[a[j].t] += ans.second;
	}
	cdq1(mid + 1, r);
}

void cdq2(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	std::sort(a + l, a + r + 1, cmp1); cdq2(l, mid);
	std::sort(a + l, a + mid + 1, cmp2); std::sort(a + mid + 1, a + r + 1, cmp2);
	clear(1, 1, n); pair < int, double > ans;
	for (int i = l, j = mid + 1; j <= r; ++ j) {
		while (i <= mid && a[i].h >= a[j].h) {
			modify(1, a[i].v, f2[a[i].t], g2[a[i].t]);
			++ i;
		}
		ans = query(1, a[j].v, n);
		if (ans.first == 0) continue;
		if (f2[a[j].t] < ans.first + 1) f2[a[j].t] = ans.first + 1, g2[a[j].t] = 0.00;
		if (f2[a[j].t] == ans.first + 1) g2[a[j].t] += ans.second;
	}
	cdq2(mid + 1, r);
}

signed main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	n = read(); int mxH = 0, V = 0;
	for (int i = 1; i <= n; ++ i) {
		a[i].t = i, a[i].h = read(), a[i].v = cpy[i] = (double) read();
		mxH = std::max(mxH, a[i].h);
	}
	std::sort(cpy + 1, cpy + n + 1);
	V = std::unique(cpy + 1, cpy + n + 1) - cpy - 1;
	for (int i = 1; i <= n; ++ i) {
		a[i].v = lower_bound(cpy + 1, cpy + V + 1, a[i].v) - cpy;
		f1[i] = f2[i] = 1, g1[i] = g2[i] = 1.000;
	}
	build(1, 1, n);
	std::sort(a + 1, a + n + 1, cmp1);
	cdq1(1, n);
	int res = 0; double tot = 0.00;
	for (int i = 1; i <= n; ++ i) res = std::max(res, f1[i]);
	for (int i = 1; i <= n; ++ i) {
		if (f1[i] == res) tot += g1[i];
	}
	printf("%lld\n", res);
	for (int i = 1; i <= n; ++ i) a[i].t = n - a[i].t + 1, a[i].h = mxH - a[i].h + 1, a[i].v = V - a[i].v + 1;
	std::sort(a + 1, a + n + 1, cmp1);
	clear(1, 1, n), cdq2(1, n);
	for (int i = 1; i <= n; ++ i) {
		if (f1[i] + f2[n - i + 1] - 1 != res) printf("%.6lf ", 0.0);
		else printf("%.6lf ", g1[i] * g2[n - i + 1] / tot);
	}
	puts("");
	return 0;
}
```

最后修改：2021 年 08 月 20 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

xbieygztgu
不错不错，我喜欢看 https://www.ea55.com/
ojvrnvtsvs
看的我热血沸腾啊https://www.ea55.com/
orzaztmfuh
不错不错，我喜欢看 https://www.ea55.com/
mzcwdjqqxe
不错不错，我喜欢看 https://www.ea55.com/
Yanws
牢师求更新

Luogu2487 [SDOI2011]拦截导弹

tony102 • 2021 年 03 月 23 日

[Link](https://www.luogu.com.cn/problem/P2487)

这道题不要去darkbzoj上交，估计是当时没加SPJ导致你无论如何都过不去

## Sol

导弹拦截大家都会

现在已经给你了导弹来的顺序，我们把这个顺序记做 $t_i$

就这么写还是有锅，因为一种方案的方案数应该是以它开头和以它结尾的方案数的成绩。所以我们把三维全部逆过来，然后再做一遍 cdq 就可以了。

此外，注意方案数相加相乘会爆`long long`，用`double`存就可以了

## Code
```cpp
#include <bits/stdc++.h>
#define int long long
// #define double long double
using namespace std;

const int SIZE = 5e4 + 5;

int n;
int f1[SIZE], f2[SIZE];
double g1[SIZE], g2[SIZE], cpy[SIZE];

struct DF {	
	int t, h; double v;
} a[SIZE];

struct node {
	int l, r, mx; double cnt;
} tree[SIZE << 2];

#define lson(p) (p << 1)
#define rson(p) (p << 1 | 1)

void clear(int p, int l, int r) {
	if (tree[p].mx == 0) return;
	tree[p].mx = 0;
	if (l == r) return;
	int mid = (l + r) >> 1;
	clear(lson(p), l, mid), clear(rson(p), mid + 1, r); 
}

int cmp1(DF a, DF b) { return a.t < b.t; }
int cmp2(DF a, DF b) { return a.h == b.h ? a.t < b.t : a.h > b.h; }

Luogu2487 [SDOI2011]拦截导弹

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

20211103 并王 (bing)

《廊桥分配》问题研究

莫比乌斯反演学习笔记

Luogu3251 [JLOI2012]时间流逝

LOJ#3346 [APIO2020]交换城市

Luogu2487 [SDOI2011]拦截导弹

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Luogu2487 [SDOI2011]拦截导弹

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款