下面这份代码，时间复杂度为 $O(n(\log n+k))$，理论上可以通过，但是 t 了三个 subtask，甚至 $n=8\times 10^4$ 的点也 t 了，$n=6000$ 的点运行了 $300$ ms。

然后我在我的电脑上造了一组 $n=5 \times 10^4,k=100$ 的数据，运行时间竟高达 $57.58$ 秒。

我不认为我的代码的正确性或时间复杂度有误。求助卡常。

#include<bits/stdc++.h>
#define ls 2*u
#define rs 2*u+1
using namespace std;
typedef long long ll;
struct nd{
	ll sum,ml,mr,mt;
};
struct sgt{
	nd t[800080];
	nd mer(nd l,nd r){
		nd ans=nd();
		ans.sum=l.sum+r.sum;
		ans.ml=max(l.ml,l.sum+r.ml);
		ans.mr=max(r.mr,r.sum+l.mr);
		ans.mt=max({l.mt,r.mt,l.mr+r.ml});
		return ans;
	}
	void push_up(ll u){
		t[u]=mer(t[ls],t[rs]);
	}
	void upd(ll u,ll le,ll ri,ll x,ll k){
		if(le==ri){
			t[u]={k,k,k,k};
			return ;
		}
		ll mid=(le+ri)/2;
		if(x<=mid) upd(ls,le,mid,x,k);
		else upd(rs,mid+1,ri,x,k);
		push_up(u);
	}
	nd que(ll u,ll le,ll ri,ll x,ll y){
		if(x>y) return {0,0,0,0};
		if(x<=le&&ri<=y){
			return t[u];
		}
		nd r1=nd(),r2=nd();
		ll mid=(le+ri)/2;
		if(x<=mid) r1=que(ls,le,mid,x,y);
		if(y>mid) r2=que(rs,mid+1,ri,x,y);
		return mer(r1,r2);
	}
}t;
ll n,m,a[200020],ans;
ll fr[200020],ne[200020],re[200020];
nd r[200020];// sum ml mr 均指右边的相关参数 
set<ll> s;
priority_queue<pair<ll,ll> > q;
void ins(ll x){
	auto it=upper_bound(s.begin(),s.end(),x);
	it--;
	ll u=*it;
	ll le=u,ri=ne[u];
	ne[le]=x;
	ne[x]=ri;
	fr[x]=le;
	fr[ri]=x;
	r[u]=t.que(1,1,n,le+1,x-1);
	r[x]=t.que(1,1,n,x+1,ri-1);
	s.insert(x);
	ll p1=x;
	for(int i=1;i<=m+5;i++){
		p1=fr[p1];
		if(p1==0) break;
	}
	vector<ll> v,k;
	v.clear(),k.clear();
	for(int i=1;i<=2*m+10;i++){
		if(1<=p1&&p1<=n) v.push_back(p1);
		p1=ne[p1];
		if(p1==n+1) break;
	}
	ll sum=0;
	for(int i=0;i<v.size();i++){
		if(i>=m-1){
			if(i>=m){
				sum-=r[v[i-m]].sum;
			}
			k.push_back(sum);
		}
		sum+=r[v[i]].sum;
	}
	for(int i=0;i<k.size();i++){
		ll u=v[i],w=v[i+m-1];
		ll res1=k[i]+r[fr[u]].mr+r[w].ml;
		re[u]=res1;
		ans=max(ans,res1);
	}
}
int main(){
//	freopen("gift1.in","r",stdin);
//	freopen("gift1.out","w",stdout);
	scanf("%lld%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		t.upd(1,1,n,i,a[i]);
		q.push({a[i],i});
	}
	nd res=t.que(1,1,n,1,n);
	if(m==0){
		printf("%lld\n",res.mt);
		return 0;
	}
	s.insert(0),s.insert(n+1);
	fr[n+1]=0,ne[0]=n+1;
	while(!q.empty()){
		ll u=q.top().first,w=q.top().second;
		q.pop();
		ins(w);
	}
	printf("%lld\n",ans);
}