70分求助

P3372 【模板】线段树 1

R浩轩泽Anmicius @ 2023-09-20 22:54:08

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+6;
int n,q,a[N],b,l,r,x;
struct Tree{
    int ans;
    int lazy_tag;
}node[N<<2];
void build_tree(int k,int l_,int r_){
    if(l_==r_){
        node[k].ans=a[l_];
        return;
    }
    int mid=(l_+r_)>>1;
    build_tree(k<<1,l_,mid);
    build_tree(k<<1|1,mid+1,r_);
    node[k].ans=node[k<<1].ans+node[k<<1|1].ans;
}
void Add(int k,int l_,int r_,int num){
    node[k].lazy_tag+=num;
    node[k].ans+=num*(r_-l_+1);
}
void push_down(int k,int l_,int r_){
    if(!node[k].lazy_tag)return;
    int mid=(l_+r_)>>1;
    Add(k<<1,l_,mid,node[k].lazy_tag);
    Add(k<<1|1,mid+1,r_,node[k].lazy_tag);
    node[k].lazy_tag=0;
}
void add_data(int k,int l_,int r_,int num){
    if(l<=l_&&r_<=r)return Add(k,l_,r_,num);
    push_down(k,l_,r_);
    int mid=(l_+r_)>>1;//所以说尽量避免取名混淆 
    if(l<=mid)add_data(k<<1,l_,mid,num);
    if(mid<r)add_data(k<<1|1,mid+1,r_,num);
    node[k].ans=node[k<<1].ans+node[k<<1|1].ans;
}
int ask_data(int k,int l_,int r_){
    if(l<=l_&&r_<=r)return node[k].ans;
    push_down(k,l_,r_);
    int mid=(l_+r_)>>1,res=0;
    if(l<=mid)res+=ask_data(k<<1,l_,mid);
    if(mid<r)res+=ask_data(k<<1|1,mid+1,r_);
    return res;
}
inline void read(int &s){
    s=0;char ch=getchar();
    int f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    s*=f;
}
int main(){
    read(n);
    read(q);
    for(int i=1;i<=n;++i)
    read(a[i]);
    build_tree(1,1,n);
    for(int i=1;i<=q;++i){
        read(b);
        read(l);
        read(r);
        if(b==1){
            read(x);
            add_data(1,1,n,x);
        }
        else printf("%d\n",ask_data(1,1,n));
    }
    return 0;
} 

by AC_love @ 2023-09-20 23:53:14

#define int long long

注意数据范围


|