这是线段树,为什么9个点RE 1个点WA

P1440 求m区间内的最小值

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

@6371pushdownchange 里面是求和
这题是最小值


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 你的 pushdownchangeadd 是多余的,但似乎不影响正确性


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;

| 下一页