题目描述
有一个长度为 n 的序列,共有编号从 0 到 m 的 m+1 个版本。第 0 个版本 A0 已知。对每个 i=1,…,m,由第 i−1 个版本得到第 i 个版本:把区间 [Li,Ri] 中的每个元素加上 vi,其余位置保持不变。
给定 q 个询问。每个询问给出 l,r,x,y,求从第 x 到第 y 个版本中,下标 l 到 r 的所有元素的平方和对 109+7 取模的结果,即
$$\left(\sum_{i=x}^{y}\sum_{j=l}^{r} A_{i,j}^2\right)\bmod(10^9+7).$$
输入格式
第一行三个整数 n,m,q。第二行 n 个整数 A0,1,…,A0,n。
接下来 m 行,每行三个整数 Li,Ri,vi,表示一次版本更新。再接下来 q 行,每行四个整数 l,r,x,y,表示一次询问。
输出格式
每个询问输出一行一个整数,表示对应的答案。
样例
4 3 3
2 3 2 2
1 1 6
1 3 3
1 3 6
2 2 2 3
1 4 1 3
4 4 2 3
180
825
8
数据范围
n,m,q≤5×104,0≤A0,j≤109+7,1≤Li≤Ri≤n,1≤l≤r≤n,0≤x≤y≤m。更新量为非负整数,现有评测中 vi≤109+7。
| 原子任务 |
分值 |
附加限制 |
| 1 |
15 |
n,m,q≤100 |
| 2 |
n,m,q≤2000 |
| 3 |
20 |
n,m≤2000,q≤20000 |
| 4 |
n,q≤20000,m≤5 |
| 5 |
n,m,q≤20000 |
| 6 |
10 |
n,m,q≤50000 |
原 PDF 题面