给定一个长度为 N 的整数序列: A1,A2,⋯,AN 。现在你有一次机会, 将其 中连续的K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数 列的最长不下降子序列最长, 请输出这个最长的长度。
最长不下降子序列是指序列中的一个子序列, 子序列中的每个数不小于在 它之前的数。
输入第一行包含两个整数 N 和 K 。
第二行包含 N 个整数 A1,A2,⋯,AN 。
输出一行包含一个整数表示答案。
5 1
1 4 2 8 5
4
对于 20% 的评测用例, 1≤K≤N≤100;
对于 30% 的评测用例, 1≤K≤N≤1000;
对于 50% 的评测用例, 1≤K≤N≤10000;
对于所有评测用例,1≤K≤N≤105,1≤Ai≤106 。
思路：动态规划，利用权值线段树维护。权值线段树能处理：全局的第k大问题，某个数在全局的出现次数，某个区间内的每个数的出现次数。但是有局限性，比如我们要处理区间第k大问题，单一的权值线段树就处理不了了，需要树套树，例如第八大奇迹这个题，树状数组套权值线段树
分考场这个题，也是树状数组套线段树，这些代码在我的其他文章中，欢迎点赞收藏。
代码：
import bisect as bis
import copy
n,k=map(int,input().split())
num=list(map(int,input().split()))
vis=copy.deepcopy(num)
vis.sort()
vis=list(set(vis))
vis=[0]+vis
num=[0]+num
"""print(vis)"""
tree=[0 for i in range((n<<2)+100)]
dp1=[0 for i in range(n+1)] #jiewei
dp2=[0 for i in range(n+1)] #kaitou
def find(x):
return bis.bisect(vis,x)
def pushup(x):
tree[x]=max(tree[x<<1],tree[x<<1|1])
return
def update(x,l,r,ind,p):
if (l==ind and r==ind):
tree[x]=p
return
mid=(r+l)>>1
if (ind<=mid):
update(x<<1,l,mid,ind,p)
if (ind>mid):
update(x<<1|1,mid+1,r,ind,p)
pushup(x)
def query(x,l,r,a,b):
if (a<=l and r<=b):
return tree[x]
mid = (r + l) >> 1
ans=0
if (mid>=a):
ans=query(x<<1,l,mid,a,b)
if (mid<b):
ans=max(ans,query(x<<1|1,mid+1,r,a,b))
return ans
ans=k
#先处理dp1
for i in range(1,n+1):
t=find(num[i])-1
#print(t,num[i])
dp1[i]=query(1,1,len(vis)-1,1,t)+1
ans=max(ans,dp1[i])
update(1,1,len(vis)-1,t,dp1[i])
tree=[0 for i in range((n<<2)+100)]
#在处理dp2 ，同时维护ans
for i in range(n,0,-1):
t=find(num[i])-1
"""print(num[i],t)"""
mid=query(1,1,len(vis)-1,t,len(vis)-1)
"""print(mid)"""
dp2[i]=mid+1
ans=max(ans,dp2[i])
update(1,1,len(vis)-1,t,dp2[i])
start=i-k-1
if (start>=1):
t1=find(num[start])-1
ans=max(ans,query(1,1,len(vis)-1,t1,len(vis)-1)+dp1[start]+k)
for i in range(k+1,n+1):
ans=max(ans,dp2[i]+k)
for i in range(1,n-k+1):
ans=max(ans,dp1[i]+k)
"""print(dp1)
print(dp2)"""
print(ans)
通过情况：
附：在评论区发现一个佬非常精简的做法，贴一下，供大家参考：
##########################输入部分
n,k=map(int,input().split())
arr=[int(i) for i in input().split()]
l=n
notk_max=0
zd=[0 for i in range(l)]
######################################代码部分
def bj(t,a,b):#t对为大于 a>b,t错为小于 a<b
if t:
return True if a>b else False
return True if a < b else False
def erf(t,dp,a):#t错为找自左往右第一个小于a，t对为找自左往右第一个大于a
l=len(dp)
if l==0:
return -1
elif l==1:
return 0 if bj(t,dp[0],a) else -1
elif l==2:
if bj(t,dp[0],a):
return 0
elif bj(t,dp[1],a):
return 1
return -1
q=0
p=l-1
while q<=p:
m=(q+p)//2
if bj(t,dp[m],a):
p=m-1
else:
q=m+1
return q if q<l else -1
def zhao2():#得出以我结尾的的最长子序列
global zd,notk_max,arr,k,l
dp =[]
for i in range(l-k):
wz=erf(True,dp,arr[i])
if wz<0:
dp.append(arr[i])
zd[i]+= len(dp)
else:
dp[wz]=arr[i]
zd[i]+=(wz+1)
if zd[i]>notk_max:
notk_max=zd[i]
def zhao1(): # 得出以我开头的最长子序列 (不包括自己)，以及k在最左侧的not_kmax
global zd, notk_max, arr, k, l
dp = []
for i in range(l-1,k,-1):
wz=erf(False,dp,arr[i])
if wz<0:
dp.append(arr[i])
else:
dp[wz]=arr[i]
#######以下为zd赋值
wz=erf(False,dp,arr[i-k-1])
if wz<0:
zd[i-k-1]= len(dp)
else:
zd[i - k - 1] = wz
########以下得出k覆盖最左 最长不下降子序列长度
notk_max = len(dp)
wz = erf(False, dp, arr[k])
if wz<0:
notk_max+=1
##############################################输出部分
zhao1()
zhao2()
print(notk_max+k)