跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#CF295A. Greg and Array

Greg and Array

题目描述

Greg 有一个数组 aa 和按顺序编号的 mm 个操作。操作 ii 将数组闭区间 [li,ri][l_i,r_i] 中的每个元素增加 did_i。

另给出 kk 个指令,指令 (xj,yj)(x_j,y_j) 表示将编号为 xj,xj+1,…,yjx_j,x_j+1,\ldots,y_j 的操作各执行一次。不同指令可能重复执行同一操作,每次都要累计。求执行完全部指令后的数组。

输入格式

第一行输入 n,m,kn,m,k。第二行输入数组的 nn 个元素。接下来 mm 行,每行输入 li,ri,dil_i,r_i,d_i。最后 kk 行,每行输入 xj,yjx_j,y_j。所有下标从 1 开始。

输出格式

输出一行 nn 个整数,表示最终数组,相邻整数用空格隔开。

数据范围

1≤n,m,k≤1051\le n,m,k\le10^5;0≤ai,di≤1050\le a_i,d_i\le10^5;1≤li≤ri≤n1\le l_i\le r_i\le n;1≤xj≤yj≤m1\le x_j\le y_j\le m。结果可能超过 32 位整数范围。

样例

2 2 2
0 5
1 2 2
2 2 3
1 2
1 1
4 12

来源

Codeforces 295A。题意按原题整理,保留原题署名;测试数据由本站独立构造。