题目大意:输入n,m,k。n个数,m个区间更新标记为1~m。n次操作,每次操作有两个数x,y表示执行第x~y个区间更新。
题解:通过差分来表示某个区间更新操作执行的次数。然后用线段树来更新区间。
#include<bits/stdc++.h>
using namespace std;
const int N=1E5+;
typedef long long ll;
ll arr[N];
ll tt[N],cnt[N];
struct stu{
ll value,add;
}tree[N+N+N];
ll l1[N],r1[N],v[N];
void bt(ll root,ll start,ll end){
tree[root].add=;
if(start==end) {
tree[root].value=arr[end];
return ;
}
ll mid=(start+end)/;
bt(root*,start,mid);
bt(root*+,mid+,end);
tree[root].value=tree[root*].value+tree[root*+].value;
}
void pushdown(ll root,ll start,ll end){
ll mid=(start+end)/;
tree[root*].value+=(mid-start+)*tree[root].add;
tree[root*+].value+=(end-mid)*tree[root].add;
tree[root*].add+=tree[root].add;
tree[root*+].add+=tree[root].add;
tree[root].add=;
}
void update(ll root,ll start,ll end,ll l,ll r,ll k){
if(r<start||l>end) return ;
if(start>=l&&end<=r){
tree[root].value+=k*(end-start+);
tree[root].add+=k;
return ;
}
pushdown(root,start,end);
ll mid=(start+end)/;
update(root*,start,mid,l,r,k);
update(root*+,mid+,end,l,r,k);
tree[root].value=tree[root*].value+tree[root*+].value;
return ;
} ll query(ll root,ll start,ll end,ll i){
if(start==end) {
if(end==i) return tree[root].value;
}
if(start>i||i>end) return ;
pushdown(root,start,end);
ll mid=(start+end)/;
return query(root*,start,mid,i)+query(root*+,mid+,end,i);
} int main()
{
ios::sync_with_stdio();
ll n,m,q;
cin>>n>>m>>q;
for(ll i=;i<=n;i++) cin>>arr[i];
for(ll i=;i<=m;i++) cin>>l1[i]>>r1[i]>>v[i];
bt(,,n);
// for(ll i=1;i<=3*n;i++) cout<<tree[i].value<<endl;
for(ll i=;i<=q;i++){
ll x,y;
cin>>x>>y;
tt[x]++;
tt[y+]--;
}
ll tmp=;
for(ll i=;i<=m;i++){
tmp+=tt[i];
cnt[i]=tmp;
}
for(ll i=;i<=m;i++){
update(,,n,l1[i],r1[i],cnt[i]*v[i]);
}
for(ll i=;i<=n;i++) cout<<query(,,n,i)<<" ";
return ;
}