全RE T_T 本地无输出

P3372 【模板】线段树 1

kobebraint @ 2024-08-02 12:07:15

cerr是调试用的,不影响正常输出

机房里好多佬也没看出来哪里有问题

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

#define ll long long
#define cl(a) memset(a,0,sizeof a)
#define szread(a,n); for(ll i=1;i<=n;i++){cin>>a[i];}
#define forn(i,n) for(ll i=1;i<=n;i++)
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define fin(a) freopen(a,"r",stdin)
#define fout(a) freopen(a,"w",stdout)
#define ferr(a) freopen(a,"w",stderr)

ll  n,m,a[1000500],segment_tree[4000500],
    op,x,y,k,lazy_tag[4000500];

void build_segment_tree(ll l,ll r,ll k){
    if(l==r){
        segment_tree[k]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build_segment_tree(l,mid,k<<1);
    build_segment_tree(mid+1,r,k<<1|1);
    segment_tree[k]=segment_tree[k<<1]+segment_tree[k<<1|1];
}

void push_down(ll l,ll r,ll mid,ll k){
    segment_tree[k<<1]+=(mid-l+1)*lazy_tag[k];
    segment_tree[k<<1|1]+=(r-mid)*lazy_tag[k];
    lazy_tag[k<<1]+=lazy_tag[k];
    lazy_tag[k<<1|1]+=lazy_tag[k];
    lazy_tag[k]=0;
}

//l,r为k包含区间,s,e修改
void addition_segment_tree(ll l,ll r,ll k,ll s,ll e,ll x){
    cerr<<1<<"#\n";
    if(s<=l&&r<=e){
        segment_tree[k]+=(e-s+1)*x;
        lazy_tag[k]+=x;
        return;
    }
    ll mid=(l+r)>>1;
    if(lazy_tag[k]&&l!=r){
        push_down(l,r,mid,k);
    }
    if(l<=mid){
        addition_segment_tree(l,mid,k<<1,s,e,x);
    }
    if(r>mid){
        addition_segment_tree(mid+1,r,k<<1|1,s,e,x);
    }
}

//l,r为k包含区间,s,e查询
ll sum_segment_tree(ll l,ll r,ll k,ll s,ll e){
    cerr<<2<<"#\n";
    if(s<=l&&e>=r){
        return segment_tree[k];
    }
    ll mid=(l+r)>>1,sum;
    if(lazy_tag[k]){
        push_down(l,r,mid,k);
    }
    cerr<<"**^\n";
    sum=sum_segment_tree(l,mid,k<<1,s,e);
    sum+=sum_segment_tree(mid+1,r,k<<1|1,s,e);
    cerr<<3<<"#\n";
    return sum;
}

int main(){
    cin>>n>>m;
    cerr<<m<<endl;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
    }
    build_segment_tree(1,n,1);
    cerr<<"*"<<m<<endl;
    for(long long i=1;i<=m;i++){
        cin>>op>>x>>y;
        cerr<<"##"<<op<<"#"<<i<<endl;
        if(op==1){
            cin>>k;
            cerr<<"4#\n";
            addition_segment_tree(1,n,1,x,y,k);
        }else{
            cerr<<"5#\n";
            cout<<sum_segment_tree(1,n,1,x,y)<<endl;
        }
    }
    return 0;
}

by zzbzwjx @ 2024-08-02 12:52:04

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

#define ll long long
//#define cl(a) memset(a,0,sizeof a)
//#define szread(a,n); for(ll i=1;i<=n;i++){cin>>a[i];}
//#define forn(i,n) for(ll i=1;i<=n;i++)
//#define copy(a,b) copy(begin(a),end(a),begin(b))
//#define fin(a) freopen(a,"r",stdin)
//#define fout(a) freopen(a,"w",stdout)
//#define ferr(a) freopen(a,"w",stderr)

ll  n,m,a[100500],segment_tree[400500],op,x,y,k,lazy_tag[400500];

void build_segment_tree(ll l,ll r,ll k){
    if(l==r){
        segment_tree[k]=a[l];
        return;
    }
    ll mid=(l+r)/2;
    build_segment_tree(l,mid,k*2);
    build_segment_tree(mid+1,r,k*2+1);
    segment_tree[k]=segment_tree[k*2]+segment_tree[k*2+1];
}

void addition(int k,int l,int r,int tag_){
    lazy_tag[k]+=tag_;
    segment_tree[k]+=(r-l+1)*tag_;
}

void push_down(ll l,ll r,ll mid,ll k){
    if(!segment_tree[k])return;
    addition(k*2,l,mid,lazy_tag[k]);
    addition(k*2+1,mid+1,r,lazy_tag[k]);
    lazy_tag[k]=0;
}

//l,r为k包含区间,s,e修改
void addition_segment_tree(ll l,ll r,ll k,ll x){
//    cerr<<1<<"#\n";
    if(x<=l&&r<=y){
        addition(k,l,r,x);
        return;
    }
    ll mid=(l+r)/2;
//    if(lazy_tag[k]&&l!=r)
        push_down(l,r,mid,k);

    if(x<=mid){
        addition_segment_tree(l,mid,k*2,x);
    }
    if(y>mid){
        addition_segment_tree(mid+1,r,k*2+1,x);
    }
    segment_tree[k]=segment_tree[k*2]+segment_tree[k*2+1];
}

//l,r为k包含区间,s,e查询
ll sum_segment_tree(ll l,ll r,ll k){
//    cerr<<2<<"#\n";
    if(x>r||y<l)return 0;
    if(x<=l&&y>=r){
        return segment_tree[k];
    }
    ll mid=(l+r)>>1,sum=0;
//    if(lazy_tag[k])
        push_down(l,r,mid,k);

//    cerr<<"**^\n";
    sum+=sum_segment_tree(l,mid,k*2);
    sum+=sum_segment_tree(mid+1,r,k*2+1);
//    cerr<<3<<"#\n";
    return sum;
}

int main(){
    cin>>n>>m;
    cerr<<m<<endl;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
    }
    build_segment_tree(1,n,1);
//    cerr<<"*"<<m<<endl;
    for(long long i=1;i<=m;i++){
        cin>>op>>x>>y;
//        cerr<<"##"<<op<<"#"<<i<<endl;
        if(op==1){
            cin>>k;
//            cerr<<"4#\n";
            addition_segment_tree(1,n,1,k);
        }else{
//            cerr<<"5#\n";
            cout<<sum_segment_tree(1,n,1)<<endl;
        }
    }
    return 0;
}

不RE了成全WA了


by kobebraint @ 2024-08-02 13:38:28

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

#define ll long long
#define cl(a) memset(a,0,sizeof a)
#define szread(a,n); for(ll i=1;i<=n;i++){cin>>a[i];}
#define forn(i,n) for(ll i=1;i<=n;i++)
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define fin(a) freopen(a,"r",stdin)
#define fout(a) freopen(a,"w",stdout)
#define ferr(a) freopen(a,"w",stderr)

ll  n,m,a[1000500],segment_tree[4000500],
    op,x,y,k,lazy_tag[4000500];

void build_segment_tree(ll l,ll r,ll k){
    if(l==r){
        segment_tree[k]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build_segment_tree(l,mid,k<<1);
    build_segment_tree(mid+1,r,k<<1|1);
    segment_tree[k]=segment_tree[k<<1]+segment_tree[k<<1|1];
}

void push_down(ll l,ll r,ll mid,ll k){
    segment_tree[k<<1]+=(mid-l+1)*lazy_tag[k];
    segment_tree[k<<1|1]+=(r-mid)*lazy_tag[k];
    lazy_tag[k<<1]+=lazy_tag[k];
    lazy_tag[k<<1|1]+=lazy_tag[k];
    lazy_tag[k]=0;
}

//l,r为k包含区间,s,e修改
void addition_segment_tree(ll l,ll r,ll k,ll s,ll e,ll x){
    if(s<=l&&r<=e){
        segment_tree[k]+=(e-s+1)*x;
        lazy_tag[k]+=x;
        return;
    }
    ll mid=(l+r)>>1;
    if(lazy_tag[k]&&l!=r){
        push_down(l,r,mid,k);
    }
    if(s<=mid){
        addition_segment_tree(l,mid,k<<1,s,e,x);
    }
    if(e>mid){
        addition_segment_tree(mid+1,r,k<<1|1,s,e,x);
    }
    segment_tree[k]=segment_tree[k<<1]+segment_tree[k<<1|1];
}

//l,r为k包含区间,s,e查询
ll sum_segment_tree(ll l,ll r,ll k,ll s,ll e){
    if(s<=l&&e>=r){
        return segment_tree[k];
    }
    if(s>r||e<l){
        return 0;
    }
    ll mid=(l+r)>>1,sum;
    if(lazy_tag[k]){
        push_down(l,r,mid,k);
    }
    if(s<=mid){
        sum=sum_segment_tree(l,mid,k<<1,s,e);
    }
    if(e>mid){
        sum+=sum_segment_tree(mid+1,r,k<<1|1,s,e);
    }
    return sum;
}

int main(){
    cin>>n>>m;
    cerr<<m<<endl;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
    }
    build_segment_tree(1,n,1);
    for(long long i=1;i<=m;i++){
        cin>>op>>x>>y;
        if(op==1){
            cin>>k;
            addition_segment_tree(1,n,1,x,y,k);
        }else{
            cout<<sum_segment_tree(1,n,1,x,y)<<endl;
        }
    }
    return 0;
}

by kobebraint @ 2024-08-02 13:43:51

目前是有输出,但是wa


by lcy0506 @ 2024-08-02 13:57:31


#include <bits/stdc++.h>
using namespace std;
long long a[1000001],sum[4000001],add[4000001];
inline void build(long long l,long long r,long long k)
{
    if(l==r)
    {
        sum[k]=a[l];
        return;
    }
    long long mid=(l+r)>>1;
    build(l,mid,k<<1);
    build(mid+1,r,k<<1|1);
    sum[k]=sum[k<<1]+sum[k<<1|1];
}
inline void Add(long long l,long long r,long long k,long long q)
{
    add[k]+=q;
    sum[k]+=q*(r-l+1);
}
inline void pushdown(long long l,long long r,long long k)
{
    if(!add[k])
    return;
    long long mid=(l+r)>>1;
    Add(l,mid,k<<1,add[k]);
    Add(mid+1,r,k<<1|1,add[k]);
    add[k]=0;
}
inline void change(long long l,long long r,long long L,long long R,long long k,long long q)
{
    if(L<=l&&r<=R)
    {
        Add(l,r,k,q);
        return;
    }
    pushdown(l,r,k);
    long long mid=(l+r)>>1;
    if(L<=mid)
    change(l,mid,L,R,k<<1,q);
    if(R>mid)
    change(mid+1,r,L,R,k<<1|1,q);
    sum[k]=sum[k<<1]+sum[k<<1|1];
}
inline long long query(long long l,long long r,long long L,long long R,long long k)
{
    if(L<=l&&r<=R)
    {
        return sum[k];
    }
    pushdown(l,r,k);
    long long mid=(l+r)>>1,res=0;
    if(L<=mid) res+=query(l,mid,L,R,k<<1);
    if(R>mid) res+=query(mid+1,r,L,R,k<<1|1);
    return res;
}
int main()
{
    long long n,m;
    cin>>n>>m;
    for(long long i=1;i<=n;i++)
    cin>>a[i];
    build(1,n,1);
    for(long long i=1;i<=m;i++)
    {
        long long p,x,y,z;
        cin>>p;
        if(p==1)
        {
            cin>>x>>y>>z;
            change(1,n,x,y,1,z);
        }
        else
        {
            cin>>x>>y;
            cout<<query(1,n,x,y,1)<<endl;
        }
    }
}//2147483647

by lcy0506 @ 2024-08-02 13:57:48

@kobebraint


by kobebraint @ 2024-08-02 14:07:50

thx


|