#P10492. [2021年联测]leftxorright

    ID: 9609 传统题 6000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-一维前缀和离线查询懒标记线段树标记复合

[2021年联测]leftxorright

题目描述

有一个长度为 nn 的序列,共有编号从 00 到 mm 的 m+1m+1 个版本。第 00 个版本 A0A_0 已知。对每个 i=1,…,mi=1,\ldots,m,由第 i−1i-1 个版本得到第 ii 个版本:把区间 [Li,Ri][L_i,R_i] 中的每个元素加上 viv_i,其余位置保持不变。

给定 qq 个询问。每个询问给出 l,r,x,yl,r,x,y,求从第 xx 到第 yy 个版本中,下标 ll 到 rr 的所有元素的平方和对 109+710^9+7 取模的结果,即

$$\left(\sum_{i=x}^{y}\sum_{j=l}^{r} A_{i,j}^2\right)\bmod(10^9+7).$$

输入格式

第一行三个整数 n,m,qn,m,q。第二行 nn 个整数 A0,1,…,A0,nA_{0,1},\ldots,A_{0,n}。

接下来 mm 行,每行三个整数 Li,Ri,viL_i,R_i,v_i,表示一次版本更新。再接下来 qq 行,每行四个整数 l,r,x,yl,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×104n,m,q\le5\times10^4,0≤A0,j≤109+70\le A_{0,j}\le10^9+7,1≤Li≤Ri≤n1\le L_i\le R_i\le n,1≤l≤r≤n1\le l\le r\le n,0≤x≤y≤m0\le x\le y\le m。更新量为非负整数,现有评测中 vi≤109+7v_i\le10^9+7。

原子任务 分值 附加限制
1 15 n,m,q≤100n,m,q\le100
2 n,m,q≤2000n,m,q\le2000
3 20 n,m≤2000n,m\le2000,q≤20000q\le20000
4 n,q≤20000n,q\le20000,m≤5m\le5
5 n,m,q≤20000n,m,q\le20000
6 10 n,m,q≤50000n,m,q\le50000

原 PDF 题面