70tps求调

rdrding @ 2025-01-04 21:56:39

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7+10;
long long n,m,a[N],q,x,y,k;
struct node{
    long long val,left,right;
}g[N];
void init(long long l,long long r,int b){
    if(l==r){
        g[b].val=a[l];
        g[b].left=l;
        g[b].right=r;
        return;
    }
    long long mid=(l+r)>>1;
    init(l,mid,b*2);
    init(mid+1,r,b*2+1);
    g[b].val=g[b*2].val+g[b*2+1].val;
    g[b].left=l;
    g[b].right=r;
}
void add(long long l,long long r,long long x,long long y,long long k,int b){
    if(l>y || r<x)return;
    if(l==r){
        g[b].val+=k;
        return;
    }
    long long mid=(l+r)>>1;
    add(l,mid,x,y,k,b*2);
    add(mid+1,r,x,y,k,b*2+1);
    g[b].val=g[b*2].val+g[b*2+1].val;
}
long long pnt(long long l,long long r,long long x,long long y,int b){
    if(l>y || r<x || x>y)return 0;
    long long ans=0;//1 3 2 3
    ans += pnt(g[b*2+1].left,g[b*2+1].right,x,y,b*2+1);
    ans += pnt(g[b*2].left,g[b*2].right,x,y,b*2);
    if(l==r){
        ans += g[b].val;
    }
    return ans;
}
int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init(1,n,1);
    while(m--){
        cin>>q>>x>>y;
        if(q==1){
            cin>>k;
            add(1,n,x,y,k,1);
        }else{
            //question
            cout<<pnt(g[1].left,g[1].right,x,y,1)<<endl;
        }
    }

    return 0;
}

by five_rice_water @ 2025-01-04 22:02:03

这个题目是区间修改 这么写是单点修改

by five_rice_water @ 2025-01-04 22:02:22

只有三个tle，数据都有点水了

by five_rice_water @ 2025-01-04 22:03:21

区间修改要用一个叫做懒惰标记的东西（LazyTag） 你可以看一下题解 贴个代码给你参考一下

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int n,m,tree[N<<2],tag[N<<2],a[N];
void pushup(int x){
    tree[x]=tree[x<<1]+tree[x<<1|1];
}
void pushdown(int l,int r,int rt){
    if(tag[rt]!=0){
        tag[rt<<1]+=tag[rt];
        tag[rt<<1|1]+=tag[rt];
        int mid = (l+r)>>1;
        tree[rt<<1]+=tag[rt]*(mid-l+1);
        tree[rt<<1|1]+=tag[rt]*(r-mid);
        tag[rt]=0;
    }
}
void build(int l,int r,int rt){
    if(l==r){
        tree[rt]=a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int c)
{
    if(L<=l&&r<=R){
        tag[rt]+=c;
        tree[rt]+=c*(r-l+1);
        return;
    }
    pushdown(l,r,rt);
    int mid = (l+r)>>1;
    if(L<=mid) update(l,mid,rt<<1,L,R,c);
    if(mid<R) update(mid+1,r,rt<<1|1,L,R,c);
    pushup(rt);
}
int query(int l,int r,int rt,int L,int R){
    if(L<=l&&r<=R){
        return tree[rt];
    }
    pushdown(l,r,rt);
    int mid = (l+r)>>1;
    int sum = 0;
    if(L<=mid) sum+=query(l,mid,rt<<1,L,R);
    if(mid<R) sum+=query(mid+1,r,rt<<1|1,L,R);
    return sum;
}
signed main(){
    cin>>n>>m;
    for(int i = 1; i<=n; i++){
        cin>>a[i];
    }
    build(1,n,1);
    for(int i= 1; i<=m; i++){
        int pos,x,y,z;
        cin>>pos>>x>>y;
        if(pos==1){
            cin>>z;
            update(1,n,1,x,y,z);
        }
        else{
            cout<<query(1,n,1,x,y)<<endl;
        }
    }
    return 0;
}