Order Statistics

Input file: standard input

Output file: standard output
Time limit: 4 seconds
Memory limit: 1024 megabytes

You are given an array a1 , a2 , . . ., an , consisting of integers, as well as integers k and m. The following
operation is performed m times on the array:

• Select i1 , i2 , . . ., ik — the positions of the k largest elements in the array a. If two elements are
equal, the element that appears earlier in the array is considered larger.

• Decrease ai1 , ai2 , . . ., aik by 1.

For x from 1 to n, let Fm,k (x) denote the value of the x-th order statistic in the array obtained from
a after applying the operation m times with the given parameter k. For x from 1 to n, the x-th order
statistic of the array a1 , a2 , . . . , an is the element that would be in position x if the array a were sorted in
non-decreasing order.
For all l, r such that 1 ≤ l ≤ r ≤ n, let Sm,k (l, r) denote the sum of Fm,k (x) for all integers x from l to r.
More formally:

r
X
Sm,k (l, r) = Fm,k (x)
x=l

You are given integers m0 and k0 . You must compute the values of Fm0 ,k0 (x) for all x from 1 to n.
After that, you must process q queries. The j-th query (1 ≤ j ≤ q) can be one of three types:

1. Compute the value of Fmj ,kj (xj ).

2. Change the value of apj to vj .

3. Compute the value of Smj ,kj (lj , rj ).

All calculations of the functions F and S are performed independently each time and do not change the
array. All changes to the array in queries of the second type are preserved for subsequent queries.

Input
The first line contains four integers n, m0 , k0 , and q (1 ≤ n ≤ 200 000, 0 ≤ m0 ≤ 109 , 1 ≤ k0 ≤ n,
0 ≤ q ≤ 200 000) — the length of the array a; the number of operations; the number of largest elements
decreased in each operation, and the number of queries.
The second line contains n integers a1 , a2 , . . . , an (−109 ≤ ai ≤ 109 , 1 ≤ i ≤ n) — the elements of the
array a.
The next q lines contain the queries. In the j-th query, the first number is tj (1 ≤ tj ≤ 3) — the type of
the j-th query.

• If tj = 1, then the next line contains three integers mj , kj , and xj (0 ≤ mj ≤ 109 , 1 ≤ kj , xj ≤ n) —

the parameters of the first type query.

• If tj = 2, then the next line contains two integers pj and vj (1 ≤ pj ≤ n, −109 ≤ vj ≤ 109 ) — the
parameters of the second type query.

• If tj = 3, then the next line contains four integers mj , kj , lj , and rj (0 ≤ mj ≤ 109 , 1 ≤ kj , lj , rj ≤ n,

lj ≤ rj ) — the parameters of the third type query.

Page 1 of 4
Output
In the first line, output n integers Fm0 ,k0 (1), Fm0 ,k0 (2), . . . , Fm0 ,k0 (n).
Then, for each first type query, output the value Fmj ,kj (xj ) on a separate line, and for each third type
query, output the value Smj ,kj (lj , rj ) — the answer to the j-th query.

Example
standard input standard output
8 3 2 16 -1 -1 0 1 1 1 1 2
3 1 2 -1 0 2 -1 4 2
3 3 2 2 6 1
1 3 2 4 -4
3 4 5 3 5 -1
1 4 5 6 -1
2 5 -1 -1
2 6 3 1
1 3 2 1 2
1 3 2 3 3
1 3 2 4 7
1 3 2 8 8
1 0 5 6 4
2 1 5 2
3 1 3 7 8
3 2 3 5 8
3 3 3 4 7
3 4 3 4 7

Note
In the example, n = 8, m0 = 3, k0 = 2, q = 16. Initially, the array a is [3, 1, 2, −1, 0, 2, −1, 4]. Let’s see
how the array will change if we apply the operation m0 times with parameter k0 :

1. The array is [3, 1, 2, −1, 0, 2, −1, 4]. The two largest elements are in positions 1 and 8. They are
decreased by 1, after which the array becomes [2, 1, 2, −1, 0, 2, −1, 3].
2. The array is [2, 1, 2, −1, 0, 2, −1, 3]. The two largest elements are in positions 1 and 8. They are
decreased by 1, after which the array becomes [1, 1, 2, −1, 0, 2, −1, 2].
3. The array is [1, 1, 2, −1, 0, 2, −1, 2]. The two largest elements are in positions 3 and 6. They are
decreased by 1, after which the array becomes [1, 1, 1, −1, 0, 1, −1, 2].

We find that after applying the operation 3 times with parameter 2 to the array a, it becomes
[1, 1, 1, −1, 0, 1, −1, 2]. If this array is sorted, it results in the array [−1, −1, 0, 1, 1, 1, 1, 2]. Thus, the order
statistics are F3,2 (1) = −1, F3,2 (2) = −1, F3,2 (3) = 0, F3,2 (4) = 1, F3,2 (5) = 1, F3,2 (6) = 1, F3,2 (7) = 1,
F3,2 (8) = 2.
In the example, we need to process 16 queries; let’s analyze the first 10 of them in detail:

1. The first query is of type t1 = 3, with parameters m1 = 3, k1 = 2, l1 = 2, r1 = 6 and requires

computing the value of S3,2 (2, 6). We have already computed the values of F3,2 (x) for x from 1 to
8, from which we find the answer to the query:
S3,2 (2, 6) = F3,2 (2) + F3,2 (3) + F3,2 (4) + F3,2 (5) + F3,2 (6) = (−1) + 0 + 1 + 1 + 1 = 2

2. The second query is of type t2 = 1, with parameters m2 = 3, k2 = 2, x2 = 4 and requires computing

the value of F3,2 (4). We have already computed it, and it equals 1.

Page 2 of 4
 3. The third query is of type t3 = 3, with parameters m3 = 4, k3 = 5, l3 = 3, r3 = 5 and requires
computing the value of S4,5 (3, 5), that is, to calculate the sum of the order statistics from the third
to the fifth in the array obtained from a after applying the operation m3 = 4 times with parameter
k3 = 5. At the time of the third query, the array a is [3, 1, 2, −1, 0, 2, −1, 4]. The five largest elements
are in positions 1, 2, 3, 6, 8. Decreasing them by 1, we get the array [2, 0, 1, −1, 0, 1, −1, 3]. Applying
the operation three more times, we get the array [−1, −2, −2, −2, −1, −1, −1, 0]. After sorting, it
becomes [−2, −2, −2, −1, −1, −1, −1, 0]. Thus, the answer to the query is

S4,5 (3, 5) = F4,5 (3) + F4,5 (4) + F4,5 (5) = (−2) + (−1) + (−1) = −4

4. The fourth query is of type t4 = 1, with parameters m4 = 4, k4 = 5, x4 = 6. After applying four

operations with parameter 5 and sorting the array a, it will be [−2, −2, −2, −1, −1, −1, −1, 0], so
the sixth order statistic is −1.

5. The fifth query is of type t5 = 2, with parameters p5 = 5 and v5 = −1. It changes the value of a5
to −1, after which the array a becomes [3, 1, 2, −1, −1, 2, −1, 4].

6. The sixth query is of type t6 = 2, with parameters p6 = 6 and v6 = 3. It changes the value of a6 to
3, after which the array a becomes [3, 1, 2, −1, −1, 3, −1, 4].

7. The seventh query requires finding the value of F3,2 (1). At the time of the seventh query, the
array a is [3, 1, 2, −1, −1, 3, −1, 4]. After applying 3 times the operation with parameter 2, it will be
[1, 1, 1, −1, −1, 2, −1, 2]. The first order statistic of this array is −1.

8. The eighth, ninth, and tenth queries require finding the values of F3,2 (3), F3,2 (4) and F3,2 (8), that
is, the third, fourth, and eighth order statistics in the array [1, 1, 1, −1, −1, 2, −1, 2]. They are equal
to −1, 1, and 2, respectively.

Scoring
The tests for this problem consist of eleven groups. Points for each group are given only if all tests of
the group and all tests of the required groups are passed. Please note that passing the example tests is
not required for some groups. Offline-evaluation means that the results of testing your solution on this
group will only be available after the end of the competition.
If there are constraints on m or k in a subtask, they apply to both m0 and k0 , as well as to the parameters
of all first and third type queries.

The table with the groups is on the next page.

Page 3 of 4
 Additional Constraints Required
Group Points Comment
n m k q Groups

0 0 – – – – – Examples.
1 4 n ≤ 1000 m ≤ 1000 – q=0 – –
2 5 – – k=1 q=0 – –
3 6 – – k=1 q ≤ 100 000 2 tj = 1 for all queries
4 7 – – k=1 q ≤ 100 000 2, 3 tj 6= 3 for all queries
5 11 – – k=2 q=0 – –
6 9 – m ≤ 106 – q=0 1 –
7 10 n ≤ 1000 – – q=0 1 –
8 7 – – – q=0 1, 2, 5 – 7 –
9 11 – – – q ≤ 100 000 1 – 3, 5 – 8 tj = 1 for all queries
10 13 – – – q ≤ 100 000 1 – 3, 5 – 9 tj 6= 2 for all queries
11 9 – – – q ≤ 100 000 0 – 10 –
12 8 – – – – 0 – 11 Offline-evaluation.

Page 4 of 4