logo Algo Beat Contest
登录 注册

题解

作者: _ZXY_  ·  发布于 2026-05-15 20:06:33  ·  最后修改于 2026-05-15 20:40:15
已通过
审核员:Lemon_zqp 强强 · 2026-05-15 20:40:15

区间加法,可以用线段树来解决。
我们每次都用线段树区间加,最后输出原序列,就是查询 的和。
时间复杂度

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+7;
struct tree{
    int tag=0,sum=0;
}tr[N*4];
int a[N],n,m;
void push(int l,int r,int id){
    int mid=(l+r)>>1,tg=tr[id].tag;
    tr[id<<1].sum+=(mid-l+1)*tg;
    tr[id<<1|1].sum+=(r-mid)*tg;
    tr[id<<1].tag+=tg;
    tr[id<<1|1].tag+=tg;
    tr[id].tag=0;
}
void add(int l,int r,int s,int t,int k,int id){
    if(l<=s&&t<=r){
        tr[id].tag+=k;
        tr[id].sum+=(t-s+1)*k;
        return;
    }
    push(s,t,id);
    int mid=(s+t)>>1;
    if(l<=mid)add(l,r,s,mid,k,id<<1);
    if(r>mid)add(l,r,mid+1,t,k,id<<1|1);
    tr[id].sum=tr[id<<1].sum+tr[id<<1|1].sum;
}
int query(int l,int r,int s,int t,int id){
    if(l<=s&&t<=r)return tr[id].sum;
    push(s,t,id);
    int ans=0;
    int mid=(s+t)>>1;
    if(l<=mid)ans+=query(l,r,s,mid,id<<1);
    if(r>mid)ans+=query(l,r,mid+1,t,id<<1|1);
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[i]=0;
        add(i,i,1,n,a[i],1);
    }
    while(m--){
		int l,r,x;
		cin>>l>>r>>x;
		add(l,r,1,n,x,1);
	}
    for(int i=1;i<=n;i++){
        cout<<query(i,i,1,n,1)<<" ";
    }
}

暂无评论

登录 后即可评论。