Array Transformer

题意翻译

先给定三个数: $n,m,u$ 其中 $1\le n\le 3\times 10^5,1\le m\le 5 \times 10^4,1\le u\le 10^9$ 下面 $n$ 行,每行一个数 $a_i$ 接下来 $m$ 行,每行四个数 $L,R,v,p$,代表查找 $[L,R]$ 这个区间所有严格小于 $v$ 的个数。 查找出来的个数叫做 $k$,接下来将 $a_p$ 更改为 $u\times k/(r-l+1)$ 最后要你输出全部修改完之后的数列, 每个数一行。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3154 [PDF](https://uva.onlinejudge.org/external/120/p12003.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12003/50f071c57d8ce0e0ecfd82014a1327d7ceae7ed2.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12003/b1dade64563b7d3030cff0926fd43a341b640a1f.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12003/26bb239ed11d0b47045182bf090b6eb09f4ca774.png)

输入输出样例

输入样例 #1

10 1 11
1
2
3
4
5
6
7
8
9
10
2 8 6 10

输出样例 #1

1
2
3
4
5
6
7
8
9
6
Explanation: There is only one instruction: L = 2, R = 8, v = 6, p = 10. There are 4 numbers
(2,3,4,5) less than 6, so k = 4. The new number in A[10] is 11 ∗ 4/(8 − 2 + 1) = 44/7 = 6.