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

E. Greg and Array

  • 传统题
  • 2000ms
  • 256MiB

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。题意按原题整理,保留原题署名;测试数据由本站独立构造。

前缀和与差分

未参加
状态
已结束
规则
XCPC
题目
6
开始于
2026-10-28 18:00
结束于
2026-10-28 23:00
持续时间
5 小时
主持人
参赛人数
17