本文主要讲解树状数组解决LIS类问题(最长上升子序列模型)的实现逻辑
提醒:需要掌握树状数组作为前置知识,了解树状数组求解LIS模型的可直接观看下文有关本题的讲解
规定:
a[1~n]为给定序列,b[1~n]记录a中各个数的下标(即初始时b[i]=i)
f[i]表示以下标为i的数为结尾的最长上升子序列的长度
先将问题简单化,用树状数组解决最基本的lis模型
给定序列a[]={1, 4, 2, 8, 5},且a[]中无重复元素,要求按序将该序列变为递增序列
若获得变化后b[],即可遍历b[]将对应下标的值依次放置使a[]排好序
遍历b[]的过程中,对于b[i], 按照规则满足a[b[j]]<a[b[i]], 其中j<i
满足升序条件后,只需知道下标小于当前数下标(即b[j]<b[i])的f[b[j]]的最大值max
那么以当前数结尾的最长上升子序列的长度f[b[i]]=max+1
待解决问题:
1.变化后b[]的求解
初始时令b[i]=i,自定义排序规则,针对LIS模型定义为a[x]<a[y],不同问题排序规则有异
x和y为规则函数所需参数,二者皆为b数组的值,利用sort函数结合排序规则对b数组排序
2.维护树状数组信息并求f[b[j]]最大值
树状数组结点存该结点f的值,同时维护前缀区间最大值
对于树状数组求区间和的模版,修改加号为max函数即可
补充:
1.b[]的值是a[]排序前的下标,但是值的顺序是a数组[]排序后的下标顺序
可理解为b[]为a[]的一个映射,排序不会改变这种映射关系,但是会改变先后顺序
2.对于当前遍历值b[i],因为b[i]的信息未更新到树状数组中,可直接用b[i]查询
3.未遍历的值无法同时满足两个条件,即a[b[k]] < a[b[i]]且b[k] < b[i],其中k>i
故其无法对f[b[i]]贡献答案,那么贡献答案的值一定在前缀中(已遍历值)
下面简述加入重复元素后LIS问题的求解
加入重复元素,排序后a[]中相等元素的下标在b[]中位置会挨在一起
由于树状数组维护前缀区间最大值,相等元素的前一个数更新后,可能会影响后一个数查询结果
通过例子可以观察到第二个数虽然不满足a[2]<a[3],却满足b[2]<b[3]
同时由于第二个数先遍历,默认满足a[2]<a[3]的条件,造成f[3]=f[2]+1结果的错误
若要避免该问题,只需将排序规则稍加修改即可,当a[x]=a[y]时,按x>y排序
如此一来,第三个数先遍历,即破坏了b[2]<b[3]的条件,再按上文方式求解可得正确结果
类比:
最长不降序子序列排序规则:若a[x]!=a[y],按a[x]<a[y]排序;否则按x<y排序
最长降序子序列排序规则:若a[x]!=a[y],按a[x]>a[y]排序;否则按x>y排序
其他要求方法类似,读者自行揣摩,笔者不再赘述
树状数组求解LIS模型的AC代码
https://www.acwing.com/activity/content/code/content/6108491/
读懂上文可用此类方法解决的题目
https://www.acwing.com/problem/content/790/
https://www.acwing.com/problem/content/898/
https://www.acwing.com/problem/content/3665/
对于本题的分析
求最长不降序子序列不是问题,问题在于修改连续k个数后怎么在原来基础上求最大长度,定义:
g[i]为以a[i]开头的最长不降序子序列的长度
f[i]为以a[i]结尾的最长不降序子序列的长度
若要修改连续k个数,可以想到存在三种情况贡献答案:
情况一:k + g[i], (i > k)
情况二:f[i] + k, (i + k <= n)
情况三:f[i] + k + g[j], (j - i > k且a[i] < a[j])
那么答案就是这三种情况的最大值
f[]的值结合上文求解不难,但是g[]的值求解则会存在一些问题
结合g[]的定义,需要知道后缀区间的最大值才能更新g[]
但树状数组只能维护前缀信息,且无法通过整个区间最值和前缀区间最值推出后缀区间最值
可以取b[]的对称值作为当前数在树状数组中结点的位置以此更新树状数组信息
如1的对称位置为n,2的对称位置为n-1,i的对称位置就是n+1-i
如此一来前后缀互换(在树状数组中的位置),问题转化为求前缀最值,树状数组又可担此重任
对于第三种情况:
若完全理解求解f和g数组的过程,那么该情况就是查询与当前位置(b[i])相差m+1的前缀最值
枚举g[j]的位置应查询满足条件的f[i]的最值(即j - i > k且a[i] < a[j])
若枚举f[i]的位置,则应与求解g[j]同样的遍历方式和对称关系查询满足条件g[j]的最值
写在最后:
原题解主要是为记录笔者的学习心得和感悟,导致废话过多,不够精简
后发现学习人数较多遂对本文进行大幅删减和修改,受能力所限篇幅还是较长,不够精炼
如有不足之处还请各位多多包涵,另外在此感谢大家的支持
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
#define ri register int
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
int t[N], f[N], g[N];
int ans, tmp;
bool cmp(ri x, ri y)
{
if(a[x] != a[y]) return a[x] < a[y];
return x < y;
}
void modify(ri k, ri x)
{
while(k <= n)
{
t[k] = max(t[k], x);
k += lowbit(k);
}
}
int query(ri k)
{
ri res = 0;
while(k)
{
res = max(res, t[k]);
k -= lowbit(k);
}
return res;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(ri i = 1; i <= n; ++ i)
{
cin >> a[i];
b[i] = i;
}
sort(b + 1, b + n + 1, cmp);
for(ri i = 1; i <= n; ++ i) //f[i]表示以a[i]结尾的最长不下降子序列长度
{
ri pos = b[i];
f[pos] = query(pos) + 1;
modify(pos, f[pos]);
tmp = 0;
if(pos + m <= n) tmp = m; //结尾后k个数变为子序列一部分 f[i] + k
ans = max(ans, f[pos] + tmp);
}
memset(t, 0, sizeof t);
for(ri i = n; i; -- i) //g[i]表示以a[i]开头的最长不下降子序列长度
{
ri pos = n + 1 - b[i];
g[b[i]] = query(pos) + 1;
modify(pos, g[b[i]]);
tmp = 0;
if(b[i] - m >= 1) tmp = m;//开头前k个数变为子序列的一部分 k + g[i]
ans = max(ans, g[b[i]] + tmp);
}
memset(t, 0, sizeof t);
for(ri i = 1; i <= n; ++ i) //开头和结尾中间k个数变为子序列一部分 f[i] + k + g[j] (a[i] <= a[j])
{
ri pos = b[i];
if(pos > m + 1)
{
tmp = query(pos - m - 1);
ans = max(ans, tmp + m + g[pos]);
}
modify(pos, f[pos]);
}
cout << ans << endl;
return 0;
}