洛谷【p1020】导弹拦截 树状数组优化求LIS

缘起

【1】中我们介绍了LIS这个经典问题的 朴素O(n^2)的dp解法 以及贪心+二分的O(nlogn)解法. 但是其实LIS还有树状数组的O(nlogn)优化~ 遂来学习之 洛谷【p1020】导弹拦截

分析

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
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹
能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系
统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截多少导
弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式
1行，若干个整数（个数<= 100000）

输出格式
2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配
备多少套这种导弹拦截系统。

输入输出样例
输入 #1复制
389 207 155 300 299 170 158 65
输出 #1复制
6
2
说明/提示
为了让大家更好地测试n方算法，本题开启spj，n方100分，nlogn200分

每点两问，按问给分

我们再来回顾O(n^2)DP的状态转移方程：dp[i]=max{dp[j]+1}(1<=j< i,a[j]<= a[i])

其中dp[i] 是以a[i]为结尾的LIS的长度. 我们在递推dp数组的时候，每次都要把dp数组扫一遍求dp[j]的最大值，时间开销比较大（O(n^2)的根源）。我们可以借助数据结构来优化这个过程。即用树状数组来维护F数组

这里主要吸收的营养是【3】.

首先【2】中指出, 树状数组解决的问题是区间单点修改以及部分和序列的求解。其实显然也是可以解决区间单点修改+a[1,…,i]中最大这种问题的——因为只需将考虑的域由区间和变成区间极值就行了.

所以我们就热血沸腾了~ 上面的DP公式不就是求max吗? 是不是可以直接套用了呢? 但是立马我们就萎了~ 因为DP公式求max的范围不仅仅是 j<i, 还有一个约束——a[j]<a[i]. 所以如果直接使用树状数组维护的话, 可能维护dp[i]的时候把dp[j]也考虑进去了, 其中a[j]>a[i]. 这就不满足dp公式了. 那么怎么解决这个问题呢?

只需要把我们树状数组维护的区间由1<=j<i 改成如下区间即可

1
对于a[i], 假设它按照从小到大的顺序排在第p位, 则我们使用树状数组维护的区间是 1<=j<p

也就是为了求dp[i], 我们将树状数组维护的区间由 1<=j<i 改成了 1<=j<p, 其中p是a[i]在原数组中从小到大的排名.为什么这是正确的呢? 首先, dp[1,p) 考察的都是< a[j] 的，这不消说（因为从小到大排名都在a[j]前面）. 但是我们进行dp递推的时候, 还是按照原序列的顺序进行递推~ 那么在用树状数组维护dp[1,p) 的时候, 比如a[k]<a[i], 但是k>i的话, 令k1(<p)是a[k]在原数组中的排名, 则因为我们是按照原数组顺序进行dp递推的. 所以虽然a[k]的排名k1先于a[i], 即dp[k1]在dp[1,p) 中，但是因为尚未考察到, 所以dp[k1]依旧是0, 对于max是没有贡献的. 所以我们的max求出的就是排名比a[i]靠前（即排名<p，亦即值<=a[i]）,而且在原数组中顺序也比a[i]靠前. 这不就是我们的dp公式吗?

所以综上所述, 我们dp数组的意义虽然还是以某个数结尾的最长LIS, 但是dp数组的排列顺序已经变掉了——即 dp[1]是以原数组中从小到大排名第一的数（即最小数）结尾的lis, dp[2]是以原数组中从小到大排名第二的数结尾的lis,…, dp[n]是以原数组从小到大中排名第n的数（即最大的数）结尾的lis.

ps: 【2】中指出了, 树状数组能做的事情, 线段树肯定都能做, 所以其实LIS也可以使用线段树优化, 只是树状数组能搞定的事情就不需要线段树出马了~

至于第二问. 我们不得不提及数学的序理论以及组合数学中著名的Dilworth定理. 【4】中讲的很清楚了~

下面是【4】的全文摘抄

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
Dilworth定理优化“序列的不下降子序列最少划分数”
应kAc的要求，写这篇文章。虽然告别竞赛了，但是帮助晚辈，特别是有可能成为我孙子的人，还是十分有意义的。
首先是定义。
偏序关系是满足自反性、反对称性、传递性的二元关系。可以用<=表示。
自反性：x<=x成立。
反对称性：a<=b 且 b<=a <=> a=b
传递性：a<=b 且 b<=c ==> a<=c
满足上述三条性质的二元关系是偏序关系，配备偏序关系的集合称为偏序集。
显然数集上的“小于或等于”是偏序关系，但是偏序关系不只可以在数集上。
可比：a与b可比，当且仅当a<=b 或 b<=a。
设全集U是一个偏序集。
链：U的子集，满足其中任意两个元素（不相同）可比。
反链：U的子集，满足其中任意两个元素（不相同）不可比。
比如，有限数集S上的最长链的长度等于|S|，最长反链长度为1.
将U分拆成很多子集称作划分。姑且把子集全为链的划分叫做链划分，全为反链叫反链划分。
有两个互相对偶的定理：
U的链划分使用的最少集合数，等于它的最大反链长度。（1）
U的反链划分使用的最少集合数，等于它的最大链长度。（2）
其中某一个叫做Dilworth定理……我记不清了……
如果我说的不清楚，请参阅任意一本组合数学的入门书籍。
那么，罗嗦了半天，来到那个问题：给定一个全为实数的序列，每次在其中选出一个不下降子序列并将其删掉。求删完整个序列所需要的选择子序列的最少次数。
比如说，1 2 4 3 5这个序列，最少要两次，第一次1 2 3 5.
虽然序列与集合不同，但这很可能与最少划分有关。不管怎么说，打算用Dilworth定理相关内容解决本题。
首先要把序列转化成集合。不同点在于序列中元素有序。考虑使用有序数对（p，v）表示原序列中的一个数。p表示位置，v表示数值。
从集合中任意取出两个元素，如何能确定前者不比后者大呢？考虑关系<=:p1<=v1&&p2<=v2。这相当于先把两个元
素按照原序列中的位置排序，再比较数值大小。这个关系是偏序关系。如此一来，两个元素可比，等价于在原序列
中，他们是不下降的。
根据（1），原题所求的次数，等于原序列的最长非增子序列的长度。
如果是求下降子序列的最小划分，相当于是求最小反链划分，等于最长不下降子序列的长度。
（完。请多指教。）

关于Dilworth定理,我的理解就是，一个序列中最少的非降序列个数就等于整个序列最长严格递减子序列的长度

根据Dilworth定理, 本题第一问是求序列的最长非增子序列，第二问是求序列的最长严格单增的子序列（注意, 为什么是严格单增的? 因为想想上面的Dilworth定理的论述最后举的那个例子~ 反链的含义是不能比较, 不能比较就不能是非降而必须是严格单增~ 因为如果相等的话, 还是可以比较的，这和Dilworth定理不符）。

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//#include "stdafx.h"
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 100005;

struct kk
{
	int val, idx; // val是数组元素的值, idx是在原数组中的索引
	bool operator<(kk &o)
	{
		return val==o.val?idx<o.idx:val>o.val; // 如果值不相等就按照值降序排序, 否则, 维持在原数组中的顺序(即稳定排序)
	}
}a[maxn];

bool cmp(kk &x, kk &y)
{
	return x.val==y.val?x.idx<y.idx:x.val<y.val;  // 如果值不相等就按照值升序排序, 否则, 维持在原数组中的顺序(即稳定排序)
}

int n, p[maxn], dp[maxn],c[maxn], ans1, ans2; // n是原数组元素个数,ans1是非增lis个数, ans2是严格单增的lis个数, p[i]是a[i]在原数组中的从小到大的排名,注意,相同元素的排名是不同的,这和离散化不同

int read(int &x)
{
	x = 0;
	int f = 1;
	char c = getchar();
	if (!~c)
	{
		return -1;
	}
	while(!isdigit(c))
	{
		if (c=='-')
		{
			f = -1;
		}
		c = getchar();
	}
	while(isdigit(c))
	{
		x = (x<<3)+(x<<1)+(c^48);
		c = getchar();
	}
	x*=f;
	return 0;
}

void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x = -x;
	}
	if (x>9)
	{
		write(x/10);
	}
	putchar(48+x%10);
}

int lowbit(int x)
{
	return x&-x;
}

int query(int i) // 询问 dp[1,...,i]中的最大值, 基于树状数组维护
{
	int ans = 0;
	while(i)
	{
		ans = max(ans, c[i]);
		i-=lowbit(i);
	}
	return ans;
}

void updata(int i, int x) // 将dp[i]改成x,然后维护树状数组c
{
	while(i<=n)
	{
		c[i] = max(c[i], x);
		i+=lowbit(i);
	}
}

int zz(int i) // 询问严格比a[i].val小的数组元素的最大排名, 如果要用upper_bound的话,还要copy一个数组出来,麻烦~ 直接用二分答案写了
{
	int lo = 0, hi = i, mid, ans = 0;
	while(lo<=hi)
	{
		mid = lo+hi>>1;
		if (a[mid].val<a[i].val)
		{
			ans = mid;
			lo = mid+1;
		}
		else
		{
			hi = mid-1;
		}
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	n = 1;
	while(~read(a[n].val))
	{
		a[n].idx = n;
		++n;
	}
	--n; // 则最后a[1,...,n]就是数组元素,这是为了维护树状数组方便——树状数组不用0索引的
	sort(a+1,a+n+1); // 降序排序, 确切讲是非增排序
	for (int i = 1;i<=n;i++)
	{
		p[a[i].idx] = i;
	} // 得到原数组中每个元素的排名p[i]定义为a[i]在原数组中从小到大的排名
	for (int i = 1;i<=n;i++) // 按照原先数组的顺序枚举数组元素
	{
		dp[p[i]] = query(p[i]-1)+1; // 得到以原数组中从小到大排名p[i]的元素为结尾的非增lis长度
		ans1 = max(ans1, dp[p[i]]); // 维护答案
		updata(p[i], dp[p[i]]); // 维护树状数组(单点更新)
	} // 得到ans1

	memset(c,0,sizeof(c));
	memset(dp,0, sizeof(dp)); // 重新初始化

	sort(a+1,a+n+1,cmp); // 升序排序, 确切讲是非降排序
	for (int i = 1;i<=n;i++)
	{
		p[a[i].idx] = i;
	}
	for (int i = 1;i<=n;i++)
	{
		dp[p[i]] = query(zz(p[i]))+1; // 得到以原数组中从小到大排名p[i]的元素为结尾的严格单增lis长度,注意, 这里是严格lis和非严格lis的不同之处——要用zz函数
		ans2 = max(ans2, dp[p[i]]); // 维护答案
		updata(p[i], dp[p[i]]); // 维护树状数组(单点更新)
	} // 得到ans2

	write(ans1);
	puts("");
	write(ans2);
	return 0;
}

ac情况

1
2
3
4
5
6
所属题目
P1020 导弹拦截
评测状态
Accepted
评测分数
200

此题让我明白了求非降lis和（严格）单增lis的不同之处~

参考

【1】https://yfsyfs.github.io/2019/08/19/poj-2533-Longest-Ordered-Subsequence-LIS-dp-%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97/

【2】https://yfsyfs.github.io/2019/10/21/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%92%8C%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E4%B9%8B%E9%97%B4%E7%9A%84%E8%81%94%E7%B3%BB/

【3】https://www.cnblogs.com/Rosebud/p/9845935.html

【4】https://blog.csdn.net/u011676717/article/details/11842809