区间加法,可以用线段树来解决。
我们每次都用线段树区间加,最后输出原序列,就是查询 到 的和。
时间复杂度 。
#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)<<" ";
}
}
暂无评论