No.2571 Lexicographic Sequence of Sequences
タグ : / 解いたユーザー数 18
作問者 :
Magentor
/ テスター :
👑
ragna
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もしくは右上の雲マークをクリックしてアカウントを作成してください。