問題一覧 > 教育的問題

No.3524 Binary Range Update, Range Sum Query

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 3
作問者 : 👑 p-adic / テスター : 👑 binap
お気に入りにしたユーザー ProblemId : 11075 / 自分の提出
問題文最終更新日: 2026-04-18 09:34:12
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
yukicoder contest 498 リアクティブコンテスト (順位表) の他の問題:

Problem Statement

This is a reactive problem (your program must run interactively with the judge's program).

 

First, $3$ positive integers $N, B, Q$ are given.

 

For a sequence $a$ of positive integers of length $N$ and a positive integer $i$ not greater than $N$, $a_i$ denotes the $i$-th component of $a$. ($a = (a_1, a_2, \ldots, a_N)$)

For a positive integer $i$ not greater than $N$, let $S_i$ be the set of all positive integers $j$ not greater than $N$ that satisfy the following.

  • There exists a non-negative integer $d$ such that $i$ is the largest integer not exceeding $2^{-d} j$, that is, $\lfloor 2^{-d} j \rfloor$.

Roughly speaking, $S_i$ is the set of all positive integers not greater than $N$ that contain $i$ at the beginning when written in binary.

 

Binary-Loving Bot is a bot that loves binary.

You and Binary-Loving Bot share a sequence $A$ of non-negative integers of length $N$, and initially $A$ satisfies the following.

  • For every positive integer $i$ not greater than $N$, $A_i = i$.

$A$ is updated by performing the following series of exchanges (hereafter called a query) $Q$ times.

  1. First, Binary-Loving Bot chooses a positive integer $i$ not greater than $N$ and a non-negative integer $d$, and tells them to you.
  2. Next, for each element $j$ of $S_i$, $A$ is updated by replacing the $j$-th component of $A$ with $A_j^d + 1$.
  3. For the updated $A$, you answer the remainder when the sum $\sum_{j \in S_i} A_j$ of $A_j$ over all elements $j$ of $S_i$ is divided by $B$. (Hereafter, this value is called the answer to this query.)

The queries must be processed strictly in order. In particular, $i, d$ are chosen only after you have finished answering the previous queries.

Input and Output

First, $N, B, Q$ are given from standard input on line $1$, separated by half-width spaces.

$N$ $B$ $Q$

After that, process $Q$ queries. Each query is carried out using standard input and output in the following format:

  1. First, the $i, d$ chosen by Binary-Loving Bot are given on $1$ line, separated by a half-width space. However, $i, d$ are given only once you have finished outputting the answers to the previous queries.
  2. $i$ $d$
    
  3. Next, output the answer to the query on $1$ line.
  4. ($\sum_{j \in S_i} A_j$ を$B$ で割った余り)
    

Finally, print a newline.

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 1.5 \times 10^6$.
  • $B$ is an integer satisfying $1 \leq B \leq 10^2$.
  • $Q$ is an integer satisfying $1 \leq Q \leq 1.5 \times 10^3$.
  • In each query, the $i, d$ chosen by Binary-Loving Bot satisfy the following.
    • $i$ is an integer satisfying $1 \leq i \leq N$.
    • $d$ is an integer satisfying $0 \leq d \leq 10^{18}$.

Notes

If you are not familiar with reactive problems, please also refer to the summary of reactive problems.

In this problem, the judge result is not guaranteed for submissions that do not follow the instructions below:

  • Strictly follow the specified output format. For example, do not insert extra spaces.
  • Each time you output, add a newline at the end and flush standard output.
  • After you have finished outputting all answers, terminate the program immediately.

Sample

Input
3 4 5
2 1
3 1
1 2
2 2
3 3

Note, however, that line $3$, the input for query number $2$, is given only after you have output the answer to query number $1$, that line $4$, the input for query number $3$, is given only after you have output the answer to query number $2$, and so on.

Output
3
0
1
1
2

Initially, $A = (1,2,3)$.

 

In query number $1$, Binary-Loving Bot chose $(i,d) = (2,1)$. Since $S_i = S_2 = \{2 \}$, first $A$ is

$\displaystyle (A_1, A_2^d + 1, A_3) = (1,2^1+1,3) = (1,3,3) $

after the update, and for the updated $A$,

$\displaystyle \sum_{j \in S_i} A_j = A_2 = 3 $

so you answer $3$, the remainder when $3$ is divided by $B = 4$.

 

In query number $2$, Binary-Loving Bot chose $(i,d) = (3,1)$. Since $S_i = S_3 = \{3 \}$, first $A$ is

$\displaystyle (A_1, A_2, A_3^d + 1) = (1,3,3^1+1) = (1,3,4) $

after the update, and for the updated $A$,

$\displaystyle \sum_{j \in S_i} A_j = A_3 = 4 $

so you answer $0$, the remainder when $4$ is divided by $B = 4$.

 

In query number $3$, Binary-Loving Bot chose $(i,d) = (1,2)$. Since $S_i = S_1 = \{1,2,3 \}$, first $A$ is

$\displaystyle (A_1^d + 1, A_2^d + 1, A_3^d + 1) = (1^2+1,3^2+1,4^2+1) = (2,10,17) $

after the update, and for the updated $A$,

$\displaystyle \sum_{j \in S_i} A_j = A_1 + A_2 + A_3 = 2 + 10 + 17 = 29 $

so you answer $1$, the remainder when $29$ is divided by $B = 4$.

 

In query number $4$, Binary-Loving Bot chose $(i,d) = (2,2)$. Since $S_i = S_2 = \{2 \}$, first $A$ is

$\displaystyle (A_1, A_2^d + 1, A_3) = (2,10^2+1,17) = (2,101,17) $

after the update, and for the updated $A$,

$\displaystyle \sum_{j \in S_i} A_j = A_2 = 101 $

so you answer $1$, the remainder when $101$ is divided by $B = 4$.

 

In query number $5$, Binary-Loving Bot chose $(i,d) = (3,3)$. Since $S_i = S_3 = \{3 \}$, first $A$ is

$\displaystyle (A_1, A_2, A_3^d + 1) = (2,101,17^3 + 1) = (2,101,4914) $

after the update, and for the updated $A$,

$\displaystyle \sum_{j \in S_i} A_j = A_3 = 4914 $

so you answer $2$, the remainder when $4914$ is divided by $B = 4$.

 

Since $Q = 5$ in this case, all queries have now been processed.

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