TLE求调

bzdss @ 2024-12-29 16:01:13

#include<bits/stdc++.h>
using namespace std;
long long ans[400004],num[100001],k[400004];
long long n,m;
long long left(long long a){
    return a*2;
}
long long right(long long a){
    return a*2+1;
}
void addd(long long l, long long r, long long nl, long long nr,long long p,long long kk){
    if(l<=nl and r>=nr){
        k[p]+=kk;
        ans[p]+=kk+kk*(nr-nl);
        return;
    }
    if(nl==nr){
        return; 
    }
    addd(l,r,nl,(nl+nr)/2,left(p),kk);
    addd(l,r,((nl+nr)/2)+1,nr,right(p),kk);
    return;
}
void jianzao(long long l,long long r,long long anss){
    //cout<<l<<' '<<r<<' '<<anss<<endl; 
    k[anss]=0;
    if(r==l){
        ans[anss]=num[r];
        return;
    }
    else{
        jianzao(l,(l+r)/2,left(anss));
        jianzao(((l+r)/2)+1,r,right(anss)) ;
        ans[anss]=ans[left(anss)]+ans[right(anss)];
        return;
    } 

}
long long find(long long l, long long r, long long nl, long long nr,long long p) {
    //cout<<nl<<' '<<nr<<' '<<p<<endl; 
    if(l<=nl and r>=nr)return ans[p]; 
    if(nl==nr){
        return 0; 
    }
    k[left(p)]+=k[p];
    k[right(p)]+=k[p];
    ans[left(p)]+=k[p]+k[p]*(((nl+nr)/2)-nl);
    ans[right(p)]+=k[p]+k[p]*(nr-(((nl+nr)/2)+1));
    long long sum=0;
    sum+=find(l,r,nl,(nl+nr)/2,left(p));
    sum+=find(l,r,((nl+nr)/2)+1,nr,right(p));
    return sum;
}
int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        cin>>num[i];
    }
    jianzao(1,n,1);
    while(m--){
        long long b,x,y,kk;
        cin>>b;
        if(b==1){
            cin>>x>>y>>kk;
            addd(x,y,1,n,1,kk);
        }
        else{
            cin>>x>>y;
            cout<<find(x,y,1,n,1)<<endl;
        }
    }
}

by dalu @ 2025-01-08 18:26:14

@bzdss

#include <iostream>
#include <cstring>
#include <vector>
#define int long long
using namespace std;

class Segment_tree{
private:
    std::vector < int > tree,tag,a;
public:
    void init(std::vector < int > v,int n){
        a = v;
        tree.resize((n << 2) + 5);
        tag.resize((n << 2) + 5);
    }
private:
    int ls(int p){return p << 1;}

    int rs(int p){return p << 1 | 1;}

    void push_up(int p){
        tree[p] = tree[ls(p)] + tree[rs(p)];//区间和
        //tree[p] = min(tree[ls(p)],tree[rs(p)]);//最小值
        //tree[p] = max(tree[ls(p)],tree[rs(p)]);//最大值
    }
public:
    void bulid(int p,int pl,int pr){
        tag[p] = 0;
        if(pl == pr){tree[p] = a[pl];return;}
        int mid = (pl + pr) >> 1;
        bulid(ls(p),pl,mid);
        bulid(rs(p),mid + 1,pr);
        push_up(p);
    }
private:
    void addtag(int p,int pl,int pr,int d){
        tag[p] += d;
        tree[p] += d * (pr - pl + 1);
    }

    void push_down(int p,int pl,int pr){
        if(tag[p]){
            int mid = (pl + pr) >> 1;
            addtag(ls(p),pl,mid,tag[p]);
            addtag(rs(p),mid + 1,pr,tag[p]);
            tag[p] = 0;
        }
    }
public:
    void update(int L,int R,int p,int pl,int pr,int d){
        if(L <= pl && pr <= R){
            addtag(p,pl,pr,d);
            return;
        }
        push_down(p,pl,pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid) update(L,R,ls(p),pl,mid,d);
        if(R > mid) update(L,R,rs(p),mid + 1,pr,d);
        push_up(p);
    }

    int query(int L,int R,int p,int pl,int pr){
        if(pl >= L && R >= pr) return tree[p];
        push_down(p,pl,pr);
        int res = 0;
        int mid = (pl + pr) >> 1;
        if(L <= mid) res += query(L,R,ls(p),pl,mid);
        if(R > mid) res += query(L,R,rs(p),mid + 1,pr);
        return res;
    }
};

vector < int > a(100005);

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    Segment_tree tree;
    tree.init(a,100000);
    tree.bulid(1,1,n);
    while(m--){
        int q,L,R,d;
        cin >> q;
        if(q == 1){
            cin >> L >> R >> d;
            tree.update(L,R,1,1,n,d);
        }else{
            cin >> L >> R;
            cout << tree.query(L,R,1,1,n) << '\n';
        }
    }
    return 0;
}