2 seconds
256 megabytes
standard input
standard output
Greg has an array a = a1, a2, ..., an and m operations.
Each operation looks as: li, ri, di, (1 ≤ li ≤ ri ≤ n).
To apply operation i to the array means to increase all array elements with numbers li, li + 1, ..., ri by
value di.
Greg wrote down k queries on a piece of paper. Each query has the following form: xi, yi, (1 ≤ xi ≤ yi ≤ m).
That means that one should apply operations with numbers xi, xi + 1, ..., yi to
the array.
Now Greg is wondering, what the array a will be after all the queries are executed. Help Greg.
The first line contains integers n, m, k (1 ≤ n, m, k ≤ 105).
The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 105) —
the initial array.
Next m lines contain operations, the operation number i is
written as three integers: li, ri, di, (1 ≤ li ≤ ri ≤ n), (0 ≤ di ≤ 105).
Next k lines contain the queries, the query number i is
written as two integers: xi, yi, (1 ≤ xi ≤ yi ≤ m).
The numbers in the lines are separated by single spaces.
On a single line print n integers a1, a2, ..., an —
the array after executing all the queries. Separate the printed numbers by spaces.
Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred
to use the cin, cout streams of the %I64dspecifier.
3 3 3 1 2 3 1 2 1 1 3 2 2 3 4 1 2 1 3 2 3
9 18 17
1 1 1 1 1 1 1 1 1
2
4 3 6 1 2 3 4 1 2 1 2 3 2 3 4 4 1 2 1 3 2 3 1 2 1 3 2 3
5 18 31 20
题目链接：here
种两棵线段树，一棵统计各种操作进行的次数，另一棵统计值。
线段树成段更新和段求和都是很基础的操作，没什么好说的。
倒是做这个题的时候得到一个深刻的教训，就是，C\C++的优先级太复杂了，
除了加减乘除这几个很确定的运算其他都应加上括号，不然出现莫民奇妙的错误真会痛苦死的，
因为优先级出问题浪费了大半天时间，以后引以为戒。
#include<cstdio>
#include<cstring>
#define N 200100
long long t[N*4],ct[N*4];
int a,b,n,m,k,d1,d2,temp;
struct cmd
{
int l,r,x;
}arr[N];
void update(long long *tree,int d,int l,int r,long long x)
{
for(l+=(1<<d),r+=(1<<d),r;l<r;l=l>>1,r=r>>1) {
if((r&1)==0) tree[r--]+=x;
if((l&1)==1) tree[l++]+=x;
//之前此处没考虑优先级写成了if(r&1==0)，结果郁闷了好久
}
if(l==r) tree[l]+=x;
}
long long get(long long *tree,int d,int idx)
{
long long ans=0;
for(idx=(1<<d)+idx;idx>0;idx=idx>>1) ans+=tree[idx];
return ans;
}
int main()
{
for(int i=0;i<4*N;i++) t[i]=ct[i]=0;
scanf("%d%d%d",&n,&m,&k);
d1=d2=1;
while( (1<<d1)<n ) d1++;
while( (1<<d2)<m ) d2++;
for(int i=0;i<n;i++) {
scanf("%d",&temp);
t[(1<<d1)+i]=(long long)temp;
}
for(int i=0;i<m;i++) scanf("%d%d%d",&arr[i].l,&arr[i].r,&arr[i].x);
for(int i=1;i<=k;i++) {
scanf("%d%d",&a,&b);
update(ct,d2,a-1,b-1,1);
}
for(int i=0;i<m;i++) {
long long inc=((long long)arr[i].x)*get(ct,d2,i);
//此处同样也因优先级问题郁闷了好久
update(t,d1,arr[i].l-1,arr[i].r-1,inc);
}
for(int i=0;i<n;i++) printf("%I64d ",get(t,d1,i));
return 0;
}