0tps求调

xuzihan1008 @ 2024-08-20 20:27:21

#include<bits/stdc++.h>
using namespace std;
long long a[100040];
int tree[400400],lazy[400400];
long long pushup(int node){
    int left_node=2*node;
    int right_node=2*node+1;
    tree[node]=tree[left_node]+tree[right_node];
}
void build_tree(int node,long long l,long long r){
    if(l==r){
        tree[node]=a[l];
        return;
    }
    else{
        long long mid=(l+r)/2;
        long long left_node=2*node;
        long long right_node=2*node+1;
        build_tree(left_node,l,mid);
        build_tree(right_node,mid+1,r);
        pushup(node);
    }
}
void pushdown(int node,long long k){
    if(lazy[node]){
        long long left_node=2*node;
        long long right_node=2*node+1;
        lazy[left_node]+=lazy[node];
        lazy[right_node]+=lazy[node];
        tree[left_node]+=lazy[node]*(k-(k/2));
        tree[right_node]+=lazy[node]*(k/2);
        lazy[node]=0;
    }
}
void update(int node,long long l,long long r,long long left,long long right,long long val){
    if(left<=l&&right>=r){
        lazy[node]+=val;
        tree[node]+=val*(r-l+1);
    }
    else{
        pushdown(node,r-l+1);
        int mid=(l+r)/2;
        int left_node=2*node;
        int right_node=2*node+1;
        if(left<=mid)update(left_node,l,mid,left,right,val);
        if(right>mid)update(right_node,mid+1,r,left,right,val);
        pushup(node);
    }
}
long long query(int node,long long l,long long r,long long left,long long right){
    if(left<=l&&right>=r){
        return tree[node];
    }
    else{
        pushdown(node,r-l+1);
        long long mid=(l+r)/2;
        long long left_node=2*node;
        long long right_node=2*node+1;
        long long left_sum=0,right_sum=0;
        if(left<=mid){
            left_sum=query(left_node,l,mid,left,right);
        }
        if(right>mid){
            right_sum=query(right_node,mid+1,r,left,right);
        }
        return left_sum+right_sum;
    }
}
int n,q;
int main(){
    scanf("%d%d",&n,&q);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build_tree(1,1,n);
    while(q--){
        int t;
        long long l,r,val;
        scanf("%d",&t);
        if(t==2){
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(1,1,n,l,r));
        }
        else if(t==1){
            scanf("%lld%lld%lld",&l,&r,&val);
            update(1,1,n,l,r,val);
        }
    }
    return 0;
}

by zhizhenyaohanyu @ 2024-08-20 20:30:58

@xuzihan1008

#include<cstdio>
#include<cstring> 
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

struct Tree
{
   long long left,right;
   long long sum,lazy;
}; 

Tree tree[900001];
long long a[900001];

void build(long long id,long long l,long long r)
{
        tree[id].left=l; tree[id].right=r;
        if (l==r) tree[id].sum=a[l];
        else
        {
            long long mid=(l+r)/2;
            build(id*2,l,mid);
            build(id*2+1,mid+1,r);
            tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
        }
}

void vlazy(long long id)
{
    long long mid=(tree[id].left+tree[id].right)/2;
    tree[id*2].sum+=(mid-tree[id].left+1)*tree[id].lazy;
    tree[id*2].lazy+=tree[id].lazy;
    tree[id*2+1].sum+=(tree[id].right-mid)*tree[id].lazy;
    tree[id*2+1].lazy+=tree[id].lazy;
    tree[id].lazy=0;
}

long long update(long long id,long long l,long long r){
        if (tree[id].left==l && tree[id].right==r)return tree[id].sum;
        else
        {
            if(tree[id].lazy!=0) vlazy(id);
            long long mid=(tree[id].left+tree[id].right)/2; 
            if (r<=mid) return update(id*2,l,r);
            else if (l>mid) return update(id*2+1,l,r);
            else
               return update(id*2,l,mid)+update(id*2+1,mid+1,r);
        }
}

void query(long long id,long long l,long long r,long long val){
        if (tree[id].left==l && r==tree[id].right)
        {
             tree[id].sum+=val*(r-l+1);
             tree[id].lazy+=val;
        } 
        else
        {
            if(tree[id].lazy!=0) vlazy(id);
            long long mid=(tree[id].left+tree[id].right)/2; 
            if (r<=mid) query(id*2,l,r,val);
            else if (l>mid) query(id*2+1,l,r,val);
            else
            {
                query(id*2,l,mid,val);
                query(id*2+1,mid+1,r,val);
            }
            tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
        }
}

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

这样 求关qwq

by xuzihan1008 @ 2024-08-20 20:33:51

@zhizhenyaohanyu 谢谢已关，但想知道为什么错了

by Stars154356 @ 2024-08-20 20:50:13

你的push_up函数使用的是long long 类型，并且你的int 全要换成long long

by Stars154356 @ 2024-08-20 20:51:47

主要是你的tree数组没开long long

by Stars154356 @ 2024-08-20 20:52:47

还有lazy数组，这两个容易爆

by Stars154356 @ 2024-08-20 20:53:31

@xuzihan1008

by xuzihan1008 @ 2024-08-20 20:56:54

@Stars154356 谢谢大佬