← 返回题目列表

Codeforces · 2080/D

D. 订单统计

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Order Statistics - 原题 PDF 第 1 页
原题PDF第8页
Order Statistics - 原题 PDF 第 2 页
原题PDF第9页
Order Statistics - 原题 PDF 第 3 页
原题PDF第10页
Order Statistics - 原题 PDF 第 4 页
原题PDF第11页
可复制的 PDF 提取文本
Open Olympiad in Informatics 2024/25. Second day
                                  Moscow, March 8th, 2025
Problem Clay. Order Statistics

     Input file:         input.txt or standard input
    Output file:       output.txt or 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
                                         Sm,k(l, r) = X 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 8 of 11

Open Olympiad in Informatics 2024/25. Second day
                                  Moscow, March 8th, 2025

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

                  input                                   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 9 of 11

Open Olympiad in Informatics 2024/25. Second day
                                  Moscow, March 8th, 2025

   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 10 of 11

Open Olympiad in Informatics 2024/25. Second day
                                Moscow, March 8th, 2025

                           Additional Constraints             Required
Group  Points                                                 Comment
                                                      Groups                n     m       k          q

  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 ̸= 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 ̸= 2 for all queries

  11      9        –         –        –     q ≤100 000     0 – 10             –

  12      8        –         –        –         –         0 – 11    Offline-evaluation.





                                      Page 11 of 11