William_Takazaki @ 2023-07-20 10:32:53
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int tr[N*4],add[N*4],a[N],n,m;
void pushup(int k){
tr[k]=min(tr[k*2],tr[k*2+1]);
}void build(int k,int l,int r){
if(l==r){
tr[k]=a[l];
return;
}int mid=l+r>>1;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
pushup(k);
}void change(int k,int l,int r,int v){
tr[k]+=v;
add[k]+=v;
}void pushdown(int k,int l,int r){
if(add[k]!=0){
int mid=l+r>>1;
change(k*2,l,mid,add[k]);
change(k*2+1,mid+1,r,add[k]);
add[k]=0;
}
}int query(int k,int l,int r,int x,int y){
if(x<=l&&r<=y)return tr[k];
pushdown(k,l,r);
int mid=l+r>>1,minn=INT_MAX;
if(x<=mid)minn=min(minn,query(k*2,l,mid,x,y));
if(y>mid)minn=min(minn,query(k*2+1,mid+1,r,x,y));
return minn;
}int main(){
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
for(i=1;i<=n;i++){
if(i==1)printf("0\n");
else if(i==2)printf("%d\n",a[1]);
else{
int x=i-m,y=i-m+1;
printf("%d\n",query(1,1,n,x,y));
}
}
return 0;
}
我也寻思着这也没问题啊QAQ
by WsW_ @ 2023-07-20 10:35:26
没有标记你怎么 pushdown
by William_Takazaki @ 2023-07-20 10:36:11
@WsW_ 怎么没有?我add
数组不就是标记吗?
by WsW_ @ 2023-07-20 10:36:53
@6371 你 pushdown
和 change
里面是求和
这题是最小值
by WsW_ @ 2023-07-20 10:37:20
@6371 这题需要 add
吗?
by WsW_ @ 2023-07-20 10:37:54
@6371 你先看清楚题目再写,不要拿到题就复制板子
by WsW_ @ 2023-07-20 10:38:53
@6371 你的 pushdown
、change
、add
是多余的,但似乎不影响正确性
by William_Takazaki @ 2023-07-20 10:38:54
az
那为什么我样例能过去?这是凑巧吗?
by WsW_ @ 2023-07-20 10:40:05
@6371 我帮你调一调
by WsW_ @ 2023-07-20 10:41:34
@6371 你看看你输出的是什么
by WsW_ @ 2023-07-20 10:42:09
@6371
int x=i-m,y=i-m+1;