样例没过求调

P3372 【模板】线段树 1

wosyioq_1367 @ 2024-07-18 14:22:29

#include<bits/stdc++.h>
using namespace std;

const int M=1e5+10;
int n,a[M],m;

struct node{
    int s,t,p;
}b[4*M];

void pushup(int p){b[p].s=b[p*2].s+b[p*2+1].s;}
void Tag(int p,int z,int l,int r){b[p].t+=z,b[p].s+=(r-l+1)*z;}
void pushdown(int p,int l,int r){
    if(b[p].t){
        Tag(p*2,b[p].t,l,r);
        Tag(p*2+1,b[p].t,l,r);
        b[p].t=0;
    }
}

int sum(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y)return b[p].s;
    pushdown(p,l,r);
    int mid=(l+r)>>1,ans=0;
    if(x<=mid)ans+=sum(p*2,l,mid,x,y);
    cout<<ans<<"\n";
    if(mid<y)ans+=sum(p*2+1,mid+1,r,x,y);
    cout<<ans<<"\n";
    return ans;
}
void build(int p,int l,int r){
    if(l==r)return b[p].s=a[l],void();
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
void upd(int p,int l,int r,int x,int y,int z){
    if(l>=x&&r<=y)return Tag(p,z,l,r);
    pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)upd(p*2,l,mid,x,y,z);
    if(mid<y)upd(p*2+1,mid+1,r,x,y,z);
    pushup(p);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            upd(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<sum(1,1,n,x,y)<<endl;
        }
    }
    return 0;
} 

样例输出:

11
8
20

我的输出:

11
8
23

by wosyioq_1367 @ 2024-07-18 14:23:06

样例输入:

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

by zzy0618 @ 2024-07-18 16:06:01

@wosyioq_1367

  1. push_down 写错了
void pushdown(int p,int l,int r){
    if(b[p].t){
        int mid=(l+r)>>1;
        Tag(p*2,b[p].t,l,mid);
        Tag(p*2+1,b[p].t,mid+1,r);
        b[p].t=0;
    }
}
  1. 要看数据范围,这题要用 long long

  2. 把调试信息删掉


by wosyioq_1367 @ 2024-07-18 16:11:19

thanks,已AC此贴结


|