問題一覧 > 通常問題

No.3122 Median of Medians of Division

レベル : / AI推定難易度 : 2650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 23
作問者 : Naru820 / テスター : kenken714 ponjuice Nzt3
お気に入りにしたユーザー ProblemId : 12179 / 自分の提出
問題文最終更新日: 2025-04-18 20:53:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
CPCTF 2025 : PPC (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A = (A_1,A_2,...,A_N)$ of length $N$. Answer the following $Q$ queries.

Each query is one of the following $2$ types.

A query of type 1 is given in the form 1 i x. It means changing $A_i$ to $x$.

A query of type 2 is given in the form 2 l r. It means finding and printing the answer to the following problem for $B = (A_{l},A_{l + 1},...,A_{r})$.

Divide $B$ into $1$ or more non-empty contiguous subarrays and compute the median of each resulting sequence. Then arrange those medians into a single sequence and compute its median.
There are $2^{r - l}$ ways to divide in total. What is the maximum possible value of this result when the division is chosen appropriately?
Here, the median of an integer sequence $X$ of length $L$ is the $\lfloor \frac{L + 1}{2}\rfloor$-th value of $X'$, where $X'$ is the sequence obtained by sorting $X$ in ascending order. Note that $\lfloor x\rfloor$ denotes the largest integer less than or equal to $x$.

Constraints

  • $1 \leq N,Q \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9$
  • For queries of type 1, $1 \leq i \leq N$
  • For queries of type 1, $1 \leq x \leq 10^9$
  • For queries of type 2, $1 \leq l \leq r \leq N$
  • All input values are integers

Input

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

Here, $\text{query}_i$ is the $i$-th query, given in one of the following forms.

$1$ $i$ $x$

$2$ $l$ $r$

Output

Let $k$ be the number of queries of type 2. Output $k$ lines. On the $i$-th line, output the answer to the $i$-th query of type 2.

Sample 1
Input
5 6
5 2 3 6 1
2 1 3
1 3 9
2 3 4
2 1 5
1 2 1
2 1 5
Output
3
6
5
5

This input contains $6$ queries.

Consider the 1st query. In this query, $B = (5,2,3)$.

If $B$ is divided into $(5,2)$ and $(3)$, their medians are $2,3$. The median of the sequence $(2,3)$ is $2$.

If $B$ is divided into the single contiguous subarray $(5,2,3)$, its median is 3, and the median of $(3)$ is 3.

It can be proved that, for any division of $B$ into contiguous subarrays, the median of their medians cannot be made $4$ or greater, so the answer is $3$.

Consider the 2nd query. In this query, $A_3$ is changed to $9$, and $A = (5,2,9,6,1)$.

Consider the 3rd query. In this query, $B = (9,6)$.

It can be proved that no matter how $B$ is divided, the median of the medians of the resulting sequences is $6$, so the answer is $6$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。