問題一覧 > 通常問題

No.2571 Lexicographic Sequence of Sequences

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 18
作問者 : Magentor / テスター : 👑 AngrySadEight ragna
お気に入りにしたユーザー ProblemId : 10386 / 自分の提出
問題文最終更新日: 2023-12-08 20:32:56
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
緑以下コンテスト Extra (順位表) の他の問題:

Problem Statement

There is a sequence of integer sequences $S$. $S=(S_{1},S_{2},\dots,S_{|S|})$ consists of all integer sequences of length between $1$ and $K$, inclusive, whose elements are all between $1$ and $M$, inclusive, arranged in lexicographic order.

Formally, $S$ is the sequence of integer sequences satisfying the following conditions. (It can be proved that such a sequence is uniquely determined.)

  • For any integer sequence $T$ of length between $1$ and $K$, inclusive, whose elements are all between $1$ and $M$, inclusive, there is exactly $1$ positive integer $i$ such that $S_{i}=T$.
  • If $i<j$, then $S_{i}$ is lexicographically smaller than $S_{j}$.

You are given an integer sequence $A=(A_1,A_2,\dots,A_N)$ whose elements are all between $1$ and $M$, inclusive. Answer the $Q$ queries described below.

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

  • 1 l r : You are given integers $l,r$. Let $B = (A_{l},A_{l+1},\dots,A_{r})$. Output the value of the integer $i$ satisfying $S_{i}=B$, modulo $998244353$.
  • 2 x y : Change the value of $A_x$ to $y$.
What is the lexicographic order of sequences?
  • $|A|<|B|$ and $(A_1,A_2,\dots,A_{|A|})=(B_1,B_2,\dots,B_{|A|})$.
  • There exists an integer $1 \leq i \leq \min(|A|,|B|)$ such that both of the following $2$ conditions hold.
    • $(A_1,A_2,\dots,A_{i-1})=(B_1,B_2,\dots,B_{i-1})$
    • $A_i<B_i$

Constraints

  • All inputs are integers.
  • $1 \leq N,M \leq 10^5$
  • $N \leq K \leq 10^9$
  • $1 \leq Q \leq 10^5$
  • $1 \leq A_i \leq M$
  • In queries of the $1$st type, $1 \leq l \leq r \leq N$
  • In queries of the $2$nd type, $1 \leq x \leq N , 1 \leq y \leq M$
  • There is at least $1$ query of the $1$st type.

Input

The input is given from Standard Input in the following format.

$N\ M\ K\ Q$
$A_1\ A_2\ \dots\ A_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

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

$1\ l\ r$
$2\ x\ y$

Output

Let $q$ be the number of queries of the $1$st type. Output $q$ lines. The $i$-th line should contain the answer to the $i$-th query of the $1$st type.

Sample

Sample 1
Input
5 2 5 4
1 1 1 1 2
1 1 5
2 3 2
1 1 5
1 2 4
Output
6
13
18
  • In the $1$st query, $B = (1,1,1,1,2)$. Also, $S = ((1),(1,1),(1,1,1),(1,1,1,1),(1,1,1,1,1),(1,1,1,1,2), \dots )$. Therefore, output $6$.
Sample 2
Input
7 8 9 10
1 8 4 6 3 6 4
1 1 7
1 2 7
1 3 5
2 7 2
2 3 5
1 3 7
1 1 4
2 1 1
2 5 6
1 4 7
Output
17875752
143005991
70104797
89470686
18162836
109388948

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