求助大佬！！样例都没过

wangjiajinself @ 2024-05-14 20:01:20

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll n,m,u;
ll a[N],ans[N],x,y,k,tip[N];
void build(ll p,ll l,ll r){
    tip[p]=0;
    if(l==r){ans[p]=a[l];return;}
    ll mid=(l+r)>>1;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    ans[p]=ans[p*2]+ans[p*2+1];
}
void add(ll nl,ll nr,ll l,ll r,ll p,ll k){
    if(l<=nl&&r>=nr){
        tip[p]+=k;ans[p]+=k*(nr-nl+1);return;
    }
    ll mid=(nl+nr)>>1;
    tip[2*p]+=k;
    tip[2*p+1]+=k;
    ans[2*p]+=(mid-nl+1)*k;
    ans[2*p+1]+=(nr-mid)*k;
    tip[p]=0;
    if(l<=mid) add(nl,mid,l,r,p*2,k);
    if(r>mid) add(mid+1,nr,l,r,p*2+1,k);
    ans[p]=ans[p*2]+ans[p*2+1];
}
ll ask(ll nl,ll nr,ll l,ll r,ll p){
    ll res=0;
    if(l<=nl&&r>=nr) return ans[p];
    ll mid=(nl+nr)>>1;
    tip[2*p]+=k;
    tip[2*p+1]+=k;
    ans[2*p]+=(mid-nl+1)*k;
    ans[2*p+1]+=(nr-mid)*k;
    tip[p]=0;
    if(l<=mid) res+=ask(nl,mid,l,r,p*2);
    if(r>mid) res+=ask(mid+1,nr,l,r,p*2+1);//r>mid
    return res;
}
int main(){
//  ios::sync_with_stdio(false);
//  cin.tie(0);
//  cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
//  for(int i=1;i<=n;i++)
//  add(1,n,i,i,1,a[i]);
    build(1,1,n);
//    for(int i=1;;i++) {
//      if(ans[i]==0) break;
//      cout<<ans[i]<<" ";
//  }
    while(m--){
        cin>>u;
        if(u==1){
            cin>>x>>y>>k;
            add(1,n,x,y,1,k);
        }
        else if(u==2){
            cin>>x>>y;
            cout<<ask(1,n,x,y,1)<<endl;
        }
    }
    return 0;
}

by lunjiahao @ 2024-05-14 20:05:48

@noipquanguojinjiang

好奇怪啊，你的 push_down 呢

by HAha20120522 @ 2024-05-14 20:09:04

@noipquanguojinjiang 懒标记不见了！？

by lunjiahao @ 2024-05-14 20:09:47

@noipquanguojinjiang

psuh_down 写挂了啊，你这板子好奇怪建议找个好的板子重新学过吧

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll n,m,u;
ll a[N],ans[N],x,y,k,tip[N];
void build(ll p,ll l,ll r){
    tip[p]=0;
    if(l==r){ans[p]=a[l];return;}
    ll mid=(l+r)>>1;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    ans[p]=ans[p*2]+ans[p*2+1];
}
void add(ll nl,ll nr,ll l,ll r,ll p,ll k){
    if(l<=nl&&r>=nr){
        tip[p]+=k;ans[p]+=k*(nr-nl+1);return;
    }
    ll mid=(nl+nr)>>1;
    if(tip[p])//这里
    {
        tip[2*p]+=k;
        tip[2*p+1]+=k;
        ans[2*p]+=(mid-nl+1)*k;
        ans[2*p+1]+=(nr-mid)*k;
        tip[p]=0;       
    }
    if(l<=mid) add(nl,mid,l,r,p*2,k);
    if(r>mid) add(mid+1,nr,l,r,p*2+1,k);
    ans[p]=ans[p*2]+ans[p*2+1];
}
ll ask(ll nl,ll nr,ll l,ll r,ll p){
    ll res=0;
    if(l<=nl&&r>=nr) return ans[p];
    ll mid=(nl+nr)>>1;
    if(tip[p])//这里
    {
        tip[2*p]+=k;
        tip[2*p+1]+=k;
        ans[2*p]+=(mid-nl+1)*k;
        ans[2*p+1]+=(nr-mid)*k;
        tip[p]=0;       
    }
    if(l<=mid) res+=ask(nl,mid,l,r,p*2);
    if(r>mid) res+=ask(mid+1,nr,l,r,p*2+1);//r>mid
    return res;
}
int main(){
//  ios::sync_with_stdio(false);
//  cin.tie(0);
//  cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
//  for(int i=1;i<=n;i++)
//  add(1,n,i,i,1,a[i]);
    build(1,1,n);
//    for(int i=1;;i++) {
//      if(ans[i]==0) break;
//      cout<<ans[i]<<" ";
//  }
    while(m--){
        cin>>u;
        if(u==1){
            cin>>x>>y>>k;
            add(1,n,x,y,1,k);
        }
        else if(u==2){
            cin>>x>>y;
            cout<<ask(1,n,x,y,1)<<endl;
        }
    }
    return 0;
}

by HAha20120522 @ 2024-05-14 20:14:04

建议:

struct tree{
  int l,r,sum;
}t[N];

by wangjiajinself @ 2024-05-14 20:24:51

谢谢，重新学个板子吧( Ĭ ^ Ĭ )