Greg and Array

题意翻译

题目描述 Greg 有一个数列 a{a1，a2，a3...an}和m个操作（不立即执行） 每个操作将以以下形式给出，如 li ri di， （1<=li<=ri<=n）.每个操作的意思是 给区间[ali,ari]中每个数加上di； Greg在纸上写下了K个问题，每个问题将以以下形式给出 如 xi，yi； (1<=xi<=yi<=m)这意味着你应该对数组执行第xi.第xi+1.第xi+2...第yi个操作 现在Greg想知道，当操作执行之后数组a将会变得怎样，请帮帮他； 输入输出格式 输入格式： 第一行包含几个整数n,m,k(1<=n,m,k<=10^5) 第二行是原始数列 接下来m行将给出m个操作，每行有三个整数，分别为 li，ri，di；（1<=li<=ri<=n）(0<=di<=10^5) 接下来k行包含k个问题，每行有两个整数，分别为 xi，yi 每行的整数将以空格隔开 输出格式： 输出最终数列 注意，请不要在C++中使用%lld标志来输出64位整数long long，推荐使用cin, cout流或者用%I64d标志 By William_Fangs

题目描述

Greg has an array $ a=a_{1},a_{2},...,a_{n} $ and $ m $ operations. Each operation looks as: $ l_{i} $ , $ r_{i} $ , $ d_{i} $ , $ (1<=l_{i}<=r_{i}<=n) $ . To apply operation $ i $ to the array means to increase all array elements with numbers $ l_{i},l_{i}+1,...,r_{i} $ by value $ d_{i} $ . Greg wrote down $ k $ queries on a piece of paper. Each query has the following form: $ x_{i} $ , $ y_{i} $ , $ (1<=x_{i}<=y_{i}<=m) $ . That means that one should apply operations with numbers $ x_{i},x_{i}+1,...,y_{i} $ 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<=10^{5}) $ . The second line contains $ n $ integers: $ a_{1},a_{2},...,a_{n} $ $ (0<=a_{i}<=10^{5}) $ — the initial array. Next $ m $ lines contain operations, the operation number $ i $ is written as three integers: $ l_{i} $ , $ r_{i} $ , $ d_{i} $ , $ (1<=l_{i}<=r_{i}<=n) $ , $ (0<=d_{i}<=10^{5}) $ . Next $ k $ lines contain the queries, the query number $ i $ is written as two integers: $ x_{i} $ , $ y_{i} $ , $ (1<=x_{i}<=y_{i}<=m) $ . The numbers in the lines are separated by single spaces.

输出格式

On a single line print $ n $ integers $ a_{1},a_{2},...,a_{n} $ — 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 %I64d specifier.

输入输出样例

输入样例 #1

3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3

输出样例 #1

9 18 17

输入样例 #2

1 1 1
1
1 1 1
1 1

输出样例 #2

2

输入样例 #3

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

输出样例 #3

5 18 31 20