MnZn代码70pts求调

SiXinchen @ 2023-08-05 20:17:24

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

long long a[10005];

struct tree{
    long long l,r,sc,la;
}t[450005];

void build(long long p,long long l,long long r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].sc=a[l];
        return;
    }
    build(p*2,l,(l+r)>>1);
    build(p*2+1,((l+r)>>1)+1,r);
    t[p].sc=t[p*2].sc+t[p*2+1].sc;
}

void spread(long long p){
    if(t[p].la){
        t[p*2].sc+=t[p].la*(t[p*2].r-t[p*2].l+1);
        t[p*2+1].sc+=t[p].la*(t[p*2+1].r-t[p*2+1].l+1);
        t[p*2].la+=t[p].la;
        t[p*2+1].la+=t[p].la;
        t[p].la=0;
    }
}

void change(long long p,long long l,long long r,long long k){
    if(l<=t[p].l&&t[p].r<=r){
        t[p].sc+=k*(t[p].r-t[p].l+1);
        t[p].la+=k;
        return;
    }
    spread(p);
    if(l<=((t[p].l+t[p].r)>>1))change(p*2,l,r,k);
    if(r>((t[p].l+t[p].r)>>1))change(p*2+1,l,r,k);
    t[p].sc=t[p*2].sc+t[p*2+1].sc;
}

long long print(long long p,long long l,long long r){
    if(l<=t[p].l&&t[p].r<=r)return t[p].sc;
    spread(p);
    long long ans=0;
    if(l<=((t[p].l+t[p].r)>>1))ans+=print(p*2,l,r);
    if(r>((t[p].l+t[p].r)>>1))ans+=print(p*2+1,l,r);
    return ans;
}

int main(){
    long long m,n;
    scanf("%lld %lld",&n,&m);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(long long i=1;i<=m;i++){
        long long xx;
        scanf("%lld",&xx);
        if(xx==1){
            long long x,y,z;
            scanf("%lld %lld %lld",&x,&y,&z);
            change(1,x,y,z);
        }
        else{
            long long x,y;
            scanf("%lld %lld",&x,&y);
            printf("%lld\n",print(1,x,y));
        }
    }
    return 0;
}

by StarryWander @ 2023-08-05 20:25:42

@SiXinchen 数组开小了，再加个 0 AC。

by DESCENDANTSOFDRAGON @ 2023-08-05 20:28:20

可以参考一下，求互关qwq

#include<bits/stdc++.h>
#define maxn 20000005
using namespace std;
long long n,k;
long long d[maxn],a[maxn],b[maxn];
void build(long long s,long long t,long long p) {//建树 
    // 对 [s,t] 区间建立线段树,当前根的编号为 p
    if(s==t)
    {
       d[p]=a[s];
       return;
    }
    long long m=s+((t-s)>>1);
    build(s,m,p*2);
    build(m+1,t,p*2+1);
    // 递归对左右区间建树
    d[p]=d[p*2]+d[(p*2)+1];
}
void update(long long l,long long r,long long c,long long s,long long t,long long p) {//区间修改（区间加上某个值） 
    //[l,r]为修改区间,c为被修改的元素的变化量,[s,t]为当前节点包含的区间,p当前节点的编号
    if (l<=s && t<=r)
    {
       d[p]+=(t-s+1)*c; 
       b[p]+=c;
       return;
    }  //当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
    long long m=s+((t-s)>>1);
    if (b[p] && s!=t) {
      //如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
       d[p*2]+=b[p]*(m-s+1);
       d[p*2+1]+=b[p]*(t-m);
       b[p*2]+=b[p];
       b[p*2+1]+=b[p];  //将标记下传给子节点
       b[p]=0;                                //清空当前节点的标记
    }
    if(l<=m)
        update(l,r,c,s,m,p*2);
    if(r>m)
        update(l,r,c,m+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}
long long getsum(long long l, long long r, long long s, long long t, long long p) {//区间查询（区间求和） 
    //[l,r]为查询区间,[s,t]为当前节点包含的区间,p为当前节点的编号
    if(l<=s && t<=r)
        return d[p];
    //当前区间为询问区间的子集时直接返回当前区间的和
    long long m=s+((t-s)>>1);
    if(b[p])
    {
       //如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
       d[p*2]+=b[p]*(m-s+1);
       d[p*2+1]+=b[p]*(t-m);
       b[p*2]+=b[p];
       b[p*2+1]+=b[p];  //将标记下传给子节点
       b[p]=0;                                //清空当前节点的标记
    }
    long long sum=0;
    if(l<=m)
        sum=getsum(l,r,s,m,p*2);
    if(r>m)
        sum+=getsum(l,r,m+1,t,p*2+1);
    return sum;
}
//单点修改 
// root 表示整棵线段树的根结点；cnt 表示当前结点个数
// long long n;
//long long cnt,root;
//long long sum[maxn*2],ls[maxn*2],rs[maxn*2];
//// 用法：update(root, 1, n, x, f); 其中 x 为待修改节点的编号
//void update(long long& p,long long s,long long t,long long x,long long f){  // 引用传参
//    if (!p) 
//       p=++cnt;  // 当结点为空时，创建一个新的结点
//    if(s==t)
//    {
//       sum[p]+=f;
//       return;
//    }
//    long long m=s+((t-s)>>1);
//    if (x<=m)
//       update(ls[p],s,m,x,f);
//    else
//       update(rs[p],m+1,t,x,f);
//    sum[p]=sum[ls[p]]+sum[rs[p]];  // pushup
//}

//区间询问 
// 用法：query(root, 1, n, l, r);
//long long query(long long p,long long s,long long t,long long l,long long r){
//    if (!p)
//       return 0;  // 如果结点为空，返回 0
//    if(s>=l && t<=r) return sum[p];
//    long long m=s+((t-s)>>1),ans=0;
//    if(l<=m) 
//      ans+=query(ls[p],s,m,l,r);
//    if(r>m)
//      ans+=query(rs[p],m+1,t,l,r);
//    return ans;
//}

int main (){
    cin>>n>>k;
    for(long long i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,1);
    while(k--)
    {
        long long opt,x,y,z;
        cin>>opt>>x>>y;
        if(opt==2)
            cout<<getsum(x,y,1,n,1)<<endl;
        else
            cin>>z,update(x,y,z,1,n,1);
    }

    return 0;
}

by SiXinchen @ 2023-08-05 20:28:41

看来是我手贱少打了一个0，已经A了

拜谢