No.2273 Point Multiply/Divide, Range Product
Note
The time limit for this problem is 5000[ms].
Problem Statement
You are given as input $3$ positive integers $N, B, Q$, a sequence $A$ of non-negative integers of length $N$, and $Q$ queries (described later).
First, we introduce some notation. For a sequence $a$ of non-negative integers and a non-negative integer $i$ less than its length, $a_i$ denotes the $1+i$-th element of $a$.
Furthermore, for $2$ non-negative integers $\ell, r$ less than the length of $a$ satisfying $\ell \leq r$, let
$\displaystyle \left( \prod_{i = \ell}^{r} a_i \right) \bmod B $
be denoted by $P_B(a,\ell,r)$.
Also, for non-negative integers $k,m$, define the non-negative integer $R_B(k,m)$ as follows:
- If $k$ is a multiple of $B$ and $m = B$, then $R_B(k,m) = B^{-1} k$.
- Otherwise, $R_B(k,m) = m k$.
Now we move on to the main problem. Each query is a tuple $(j,m,\ell,r)$ of $4$ non-negative integers $j,m,\ell, r$ satisfying $j < N$ and $\ell \leq r < N$.
A query $(j,m,\ell,r)$ is processed as follows:
- First, update $A$ by replacing the value of the $1+j$-th element of $A$ from $A_j$ to $R_B(A_j,m)$.
- Next, find $P_B(A,\ell,r)$ for the updated $A$. (Hereafter, this value is called the answer to that query.)
Process all $Q$ queries in the given order.
Input
The input is given from standard input in the following format:
- The $1$st line contains $N, B, Q$, separated by single-byte spaces.
- The $2$nd line contains the elements of $A$, separated by single-byte spaces.
- For each positive integer $q$ not exceeding $Q$, line $2 + q$ contains the components of the $q$-th query $(j,m,\ell,r)$, separated by single-byte spaces.
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^5$
- $B$ is an integer satisfying $1 \leq B \leq 10^9$
- $Q$ is an integer satisfying $1 \leq Q \leq 10^5$
- For every non-negative integer $i$ less than $N$, $A_i$ is an integer satisfying $0 \leq A_i \leq 10^{18}$
- Every query $(j,m,\ell,r)$ satisfies the following:
- $j$ is an integer satisfying $0 \leq j < N$
- $m$ is an integer satisfying $0 \leq m \leq 10^{18}$
- $\ell$ and $r$ are integers satisfying $0 \leq \ell \leq r < N$
Output
For each positive integer $q$ not exceeding $Q$, output the answer to the $q$-th query on line $q$.
Print a newline at the end.
Sample
Sample 1
Input
1 2 1 1 0 3 0 0
Output
1
We process the query $(j,m,\ell,r) = (0,3,0,0)$. $A = (1)$ is updated to
$\displaystyle (R_B(A_0,m)) = (R_2(1,3)) = (3 \times 1) = (3) $
and for the updated $A$ we have
$\displaystyle P_B(A,\ell,r) = P_2(A,0,0) = \left( \prod_{i = 0}^{0} A_i \right) \bmod 2 = 3 \bmod 2 = 1 $
so the answer to this query is $1$. Since $Q = 1$ here, all processing is now finished.
Sample 2
Input
2 3 1 1 2 0 2 0 1
Output
1
We process the query $(j,m,\ell,r) = (0,2,0,1)$. $A = (1,2)$ is updated to
$\displaystyle (R_B(A_0,m),A_1) = (R_3(1,2),2) = (2 \times 1,2) = (2,2) $
and for the updated $A$ we have
$\displaystyle P_B(A,\ell,r) = P_3(A,0,1) = \left( \prod_{i = 0}^{1} A_i \right) \bmod 3 = (2 \times 2) \bmod 3 = 4 \bmod 3 = 1 $
so the answer to this query is $1$. Since $Q = 1$ here, all processing is now finished.
Sample 3
Input
2 3 2 6 2 1 2 0 1 0 3 0 0
Output
0 2
First, we process the $1$st query $(j,m,\ell,r) = (1,2,0,1)$. $A = (6,2)$ is updated to
$\displaystyle (A_0,R_B(A_1,m)) = (6,R_3(2,2)) = (6,2 \times 2) = (6,4) $
and for the updated $A$ we have
$\displaystyle P_B(A,\ell,r) = P_3(A,0,1) = \left( \prod_{i = 0}^{1} A_i \right) \bmod 3 = (6 \times 4) \bmod 3 = 24 \bmod 3 = 0 $
so the answer to this query is $0$.
Next, we process the $2$nd query $(j,m,\ell,r) = (0,3,0,0)$. $A = (6,4)$ is updated to
$\displaystyle (R_B(A_0,m),A_1) = (R_3(6,3),4) = (3^{-1} \times 6,4) = (2,4) $
and for the updated $A$ we have
$\displaystyle P_B(A,\ell,r) = P_3(A,0,0) = \left( \prod_{i = 0}^{0} A_i \right) \bmod 3 = 2 \bmod 3 = 2 $
so the answer to this query is $2$. Since $Q = 2$ here, all processing is now finished.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。