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.