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

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;
}

by William_Takazaki @ 2023-07-20 10:43:53

@WsW_ 这有问题吗？就是 i 前面 m 个数的位置啊

by WsW_ @ 2023-07-20 10:46:40

@6371

#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);
}int query(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tr[k];
    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);
    puts("0");
    for(i=2;i<=n;i++){
        int x=max(i-m,1),y=i-1;
        printf("%d\n",query(1,1,n,x,y));
    }
    return 0;
}

by WsW_ @ 2023-07-20 10:47:06

@6371 改完了，已 \mathtt{AC}

by WsW_ @ 2023-07-20 10:48:17

@6371 看注释

#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);
}int query(int k,int l,int r,int x,int y){//pushdown要删掉，不然最后一个点会超时 
    if(x<=l&&r<=y)return tr[k];
    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);
    puts("0");//先输出个0，不然会乱。 
    for(i=2;i<=n;i++){
        int x=max(i-m,1),y=i-1;//这里要改 
        printf("%d\n",query(1,1,n,x,y));
    }
    return 0;
}

by WsW_ @ 2023-07-20 10:50:49

@6371

x=i-m,y=i-m+1;

显然是错的，我要你求的是第 i 个数的前 m 项的最小值，你这求的是什么？
带入 i=4,m=3 你的 x=1,y=2 求的是 1\sim2 之间的最小值，要求的是 1\sim3之间的最小值

by William_Takazaki @ 2023-07-20 10:51:49

@WsW_ 感谢

by WsW_ @ 2023-07-20 10:52:14

@6371 另外 n\le10^6 不建议用线段树。
你谷神机跑得贼拉快，考场估计就 \mathtt{TLE} 了

by WsW_ @ 2023-07-20 10:55:31

@6371 不妨给我互关，下次能帮你调代码

by William_Takazaki @ 2023-07-20 12:51:36

@WsW_ 呵呵，两个月前我用RMQ做，全**MLE