12003 - Array Transformer

本題給定一個大小為 n 的陣列，其元素分別為A[1], A[2], ..., A[n]，將它經由 m 個指令轉換後輸出，每道指令格式為(L, R, v, p)，首先計算從A[L]到A[R](包含兩者)中，其值嚴格地小於 v 的個數，假設共 k 個，然後將A[p]的值改為 u*k/(R-L+1)只取整數的部份。

Input 

輸入的第一列有三個整數 n, m, u(1 <= n <= 300,000; 1 <= m <= 50,000; 1 <= u <= 1,000,000,000)，接下來的 n 列每列一個整數表示陣列的元素A[i](1 <= A[i] <= u)，再接下來的 m 列為轉換的指令，共有四個整數L, R, v, p(1 <= L <= R <= n; 1 <= v <= u; 1 <= p <= n)。

Output 

請輸出 n 列，依序把陣列中的每個元素印出來。

Sample Input 

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

Sample Output 

1
2
3
4
5
6
7
8
9
6

只有一道指令：L=2, R=8, v=6, p=10，共有4個數(2, 3, 4, 5)小於6，所以 k = 4，因此A[10]設為 11*4/(8-2+1) = 44/7 = 6(只取整數)。

---

原文出處