1 solutions

  • 0
    @ 2022-8-16 22:27:34
    #include <bits/stdc++.h>
    using namespace std;
    #define accelerate ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    #define int long long
    #define mod 1000000007
    #define ll unsigned long long
    #define PII pair<int,int>
    #define INF 0x3f3f3f3f
    const int N=1e6+100;
    int n,m,k,x,y,T,opt;
    struct Node{
    	int l,r,sum;
    }tree[N<<4];
    int a[N],tag[N];
    void build(int l,int r,int node){
    	tree[node].l=l;
    	tree[node].r=r;
    	if(l==r){
    		tree[node].sum=a[l];
    		return ;
    	}
    	int mid=(l+r)>>1;
    	build(l,mid,node<<1);
    	build(mid+1,r,node<<1|1);
    	tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
    }
    void apply(int node,int val){
    	tree[node].sum+=(tree[node].r-tree[node].l+1)*val;
    	tag[node]+=val;
    }
    void pushdown(int node){
    	if(!tag[node]) return ;
    	apply(node<<1,tag[node]);apply(node<<1|1,tag[node]);
    	tag[node]=0;
    }
    int query(int node,int L,int R){
    	if(L>tree[node].r||R<tree[node].l) return 0;
    	else if(L<=tree[node].l&&R>=tree[node].r){
    		return tree[node].sum;
    	}
    	else{
    		pushdown(node);
    		int ret=0;
    		int mid=(tree[node].l+tree[node].r)>>1;
    		if(L<=mid) ret+=query(node<<1,L,R);
    		if(R>=mid) ret+=query(node<<1|1,L,R);
    		return ret;
    	}
    }
    void update(int node,int L,int R,int k){
    	if(L>tree[node].r||R<tree[node].l) return ;
    	else if(L<=tree[node].l&&R>=tree[node].r){
    		apply(node,k);
    		return ;
    	}
    	else{
    		pushdown(node);
    		int mid=(tree[node].l+tree[node].r)>>1;
    		if(L<=mid) update(node<<1,L,R,k);
    		if(R>mid) update(node<<1|1,L,R,k);
    		tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
    	}
    }
    signed main(){
    	accelerate;
    	cin>>n>>m;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	build(1,n,1);
    	while(m--){
    		cin>>opt>>x>>y;
    		if(opt==1){
    			cin>>k;
    			update(1,x,y,k);
    		}
    		else{
    			cout<<query(1,x,y)<<"\n";
    		}
    	}
    	return 0;
    } 
    
    • 1

    Information

    ID
    6529
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    (None)
    # Submissions
    11
    Accepted
    4
    Uploaded By