题意
等价于给一个数列,每次对一个长度为$K$的连续区间减一
为最多操作多少次
题解:
看样例猜的贪心,10分钟敲了个线段树就交了...
从1开始,找$[i,i+K]$区间的最小值,然后区间减去最小值,答案加上最小值即可...
这个思路,后来我看博客上的总结,应该是没问题的,
可是,依旧不知道线段树写的对不对..因为是假数据...
#include <bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pp pair<int,int>
#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)
#define per(ii,a,b) for(int ii=a;ii>=b;ii--)
#define show(x) cout<<#x<<"="<<x<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showa(a,b) cout<<#a<<'['<<b<<"]="<<a[b]<<endl
#define print(x) cout<<#x<<"="<<x<<' '
#define ptline() cout<<endl
using namespace std;
const int maxn=1e5+10;
const int maxm=1e6+10;
const ll INF=0x3f3f3f3f;
int casn,n,m,k;
ll cnt[maxn];
struct node {
int l,r;ll mn,tag;
}lst[maxm];
#define nd lst[now]
#define ndl lst[now<<1]
#define ndr lst[now<<1|1] void maketree(int s,int t,int now){
lst[now]=(node){s,t,cnt[s],0};
if(s==t) return ;
maketree(s,(s+t)/2,now<<1);
maketree((s+t)/2+1,t,now<<1|1);
lst[now].mn=min(lst[now<<1].mn,lst[now<<1|1].mn);
}
void pushdown(int now){
if(nd.tag){
ndl.tag+=nd.tag;
ndr.tag+=nd.tag;
ndl.mn+=nd.tag;
ndr.mn+=nd.tag;
nd.tag=0;
}
}
void pushup(int now){
nd.mn=min(ndl.mn,ndr.mn);
}
void update(int s,int t,int x,int now){
if(s>nd.r||t<nd.l) return;
if(s<=nd.l&&t>=nd.r){
nd.tag+=x;
nd.mn+=x;
return;
}
pushdown(now);
update(s,t,x,now<<1);
update(s,t,x,now<<1|1);
pushup(now);
}
ll query(int s,int t,int now){
if(s>nd.r||t<nd.l) return INF<<2;
if(s<=nd.l&&t>=nd.r) return nd.mn;
pushdown(now);
return min(query(s,t,now<<1),query(s,t,now<<1|1));
} int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
cin>>casn;
while(casn--){
cin>>n>>m;
rep(i,1,n){
scanf("%lld",cnt+i);
}
maketree(1,n,1);
ll ans=0;
for(int i=1;i<=n-m+1;i++){
ll x=query(i,i+m-1,1);
if(x==INF<<2) continue;
update(i,i+m-1,-x,1);
ans+=x;
// show3(i,x,ans);
}
printf("%lld\n",ans);
} #ifdef test
fclose(stdin);fclose(stdout);system("out.txt");
#endif
return 0;
}