辽宁省建设厅投诉网站,网页设计培训图片,哈尔滨网站建设赚钱么,学生组织网站建设样例输入#xff1a;
5 1
1 4 2 8 5
样例输出#xff1a;
4
分析#xff1a;看到这种对其中连续k个数进行修改的我们就应该想到答案是由三部分组成#xff0c;因为求的是最长不下降子序列#xff0c;那么我们可以找到一个最合适的断点i#xff0c;使得答案是由区间[1…
样例输入
5 1
1 4 2 8 5
样例输出
4
分析看到这种对其中连续k个数进行修改的我们就应该想到答案是由三部分组成因为求的是最长不下降子序列那么我们可以找到一个最合适的断点i使得答案是由区间[1,i],[i1,ik],[ik1,n]三部分组成其中区间[i1,ik]里面的数是可以任意变化的那么我们只要在区间[1,i]和区间[ik1,n]中找到一个最长不下降子序列b1,b2,……,bm那么我们就可以将区间[i1,ik]中的所有数变为某个bj使得最长不下降子序列的长度为mk所以现在我们的关键问题就是为了求取m。
一般这种问题就是要设置一个前缀和一个后缀表示含义如下
f1[i]表示a[1~i]中以a[i]结尾的最长不下降子序列的长度 f2[i]表示a[i~n]中以a[i]开头的最长不下降子序列的长度
这两个数组显然可以用权值线段树预处理出来
f1[i]:就是每次在加入a[i]之前先看一下线段树中以小于等于a[i]的值结尾的最长不下降子序列的长度的最大值然后在这个基础上1即可得到
f2[i]这个要从后往前遍历这个是在每次加入a[i]之前先看一下线段树中以大于等于a[i]的值开头的最长不下降子序列的长度的最大值然后在这个基础上1即可得到
注意当求出这个值后要用f数组对权值线段树进行更新
那么我们枚举前半段区间的最长不下降子序列端点i那么也就代表最长不下降子序列是由a[1~i]中的一部分和[i1~ik]中的全部以及a[ik1,n]中的一部分组成由于我们枚举的前半段区间的最长不下降子序列的末尾那么我们就要在区间[ik1,n]中找到以大于等于a[i]的值开头的最长不下降子序列的长度最大值这个直接在求解f2[]过程中刚好可以利用权值线段树得到。
答案还有可能就是只有两段区间这个要分两种情况一种是只有a[1~i]中的一部分和[i1~ik]中的全部或者是只有[i1~ik]中的全部以及a[ik1,n]中的一部分组成这两种情况直接用for循环遍历一遍即可得到无非就是一种只用到f1[]另一种只用到f2[]。
细节见代码
#includecstdio
#includeiostream
#includealgorithm
#includecstring
#includemap
#includequeue
#includevector
#includecmath
using namespace std;
const int N5e510;
int l[N],r[N],mx[N];
int a[N];
int f1[N],f2[N];
/*
f1[i]表示a[1~i]中以a[i]结尾的最长不下降子序列的长度
f2[i]表示a[i~n]中以a[i]开头的最长不下降子序列的长度
*/
vectorintalls;
int find(int x)
{return lower_bound(alls.begin(),alls.end(),x)-alls.begin()1;
}
void pushup(int id)
{mx[id]max(mx[id1],mx[id1|1]);
}
void build(int id,int L,int R)
{l[id]L;r[id]R;mx[id]0;if(LR) return ;int midLR1;build(id1,L,mid);build(id1|1,mid1,R);pushup(id);
}
void update_point(int id,int pos,int val)
{if(l[id]r[id]){mx[id]val;return ;}int midl[id]r[id]1;if(posmid) update_point(id1,pos,val);else update_point(id1|1,pos,val);pushup(id);
}
int query_interval(int id,int L,int R)
{if(l[id]Lr[id]R) return mx[id];int midl[id]r[id]1;int ans0;if(Lmid) ansmax(ans,query_interval(id1,L,R));if(mid1R) ansmax(ans,query_interval(id1|1,L,R));return ans;
}
int main()
{int n,k;cinnk;for(int i1;in;i){scanf(%d,a[i]);alls.push_back(a[i]); }sort(alls.begin(),alls.end());alls.erase(unique(alls.begin(),alls.end()),alls.end());for(int i1;in;i)a[i]find(a[i]);build(1,1,alls.size());for(int i1;in;i){f1[i]query_interval(1,1,a[i])1;update_point(1,a[i],f1[i]);}int ans0;build(1,1,alls.size());for(int in;i1;i--){f2[i]query_interval(1,a[i],alls.size())1;update_point(1,a[i],f2[i]);if(ik){ansmax(ans,f1[i-k-1]kquery_interval(1,a[i-k-1],alls.size()));ansmax(ans,kf2[i]);}if(ikn) ansmax(ans,kf1[i]);}printf(%d\n,ans);return 0;
}
