线段树的区间更新与区间求和...一颗这样的线段树用两次...
先扫描1~k...用线段树统计出每个操作执行的次数...
那么每个操作就变成了 op. l , op.r , op.c= times* op.c
清空线段树..将初始的a1,a2~~an放入..用每个操作来更新值~~
Program:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include <ctime>
#include<queue>
#include<algorithm>
#include<cmath>
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 100005
using namespace std;
struct node
{
ll l,r,c;
}op[MAXN];
ll sum[MAXN<<2],col[MAXN<<2],a[MAXN];
int n,m,k;
void PushDown(ll len,int now)
{
if (!col[now]) return;
col[now<<1]+=col[now];
col[(now<<1)|1]+=col[now];
sum[now<<1]+=col[now]*(len-(len>>1));
sum[(now<<1)|1]+=col[now]*(len>>1);
col[now]=0;
return;
}
void update(int L,int R,ll c,int l,int r,int now)
{
if (L<=l && R>=r)
{
sum[now]+=(r-l+1)*c;
col[now]+=c;
return;
}
int mid=(l+r)/2;
PushDown(r-l+1,now);
if (L<=mid) update(L,R,c,l,mid,now<<1);
if (R>mid) update(L,R,c,mid+1,r,(now<<1)|1);
sum[now]=sum[now<<1]+sum[(now<<1)|1];
return;
}
ll query(int L,int R,int l,int r,int now)
{
ll ans=0;
if (L<=l && R>=r) return sum[now];
int mid=(l+r)/2;
PushDown(r-l+1,now);
if (L<=mid) ans+=query(L,R,l,mid,now<<1);
if (R>mid) ans+=query(L,R,mid+1,r,(now<<1)|1);
return ans;
}
int main()
{
int i;
while (~scanf("%d%d%d",&n,&m,&k))
{
memset(sum,0,sizeof(sum));
memset(col,0,sizeof(col));
for (i=1;i<=n;i++) scanf("%I64d",&a[i]);
for (i=1;i<=m;i++) scanf("%I64d%I64d%I64d",&op[i].l,&op[i].r,&op[i].c);
for (i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
update(x,y,1,1,m,1);
}
for (i=1;i<=m;i++)
{
ll x;
x=query(i,i,1,m,1);
op[i].c*=x;
}
memset(sum,0,sizeof(sum));
memset(col,0,sizeof(col));
for (i=1;i<=n;i++) update(i,i,a[i],1,n,1);
for (i=1;i<=m;i++) update(op[i].l,op[i].r,op[i].c,1,n,1);
for (i=1;i<=n;i++) printf("%I64d ",query(i,i,1,n,1));
printf("\n");
}
return 0;
}