Ex - I like Query Problem

AtCoder

IDabc256_h

Time8000ms

Memory256MB

Difficulty—

You are given $N$, $Q$, and $A=(a_1,\ldots,a_N)$. Process $Q$ queries described below. Each query is of one of the following three kinds: * `1 L R x`: for $i=L,L+1,\dots,R$, update the value of $a_i$ to $\displaystyle \left\lfloor \frac{a_i}{x} \right\rfloor$. * `2 L R y`: for $i=L,L+1,\dots,R$, update the value of $a_i$ to $y$. * `3 L R`: print $\displaystyle\sum_{i=L}^R a_i$. ## Constraints * $1 \leq N \leq 5 \times 10^5$ * $1 \leq Q \leq 10^5$ * $1 \leq L \leq R \leq N$ * $1 \leq a_i \leq 10^5$ * $2 \leq x \leq 10^5$ * $1 \leq y \leq 10^5$ * All values in input are integers. ## Input Input is given from Standard Input in the following format, where $\text{query}_i$ denotes the $i$\-th query to be processed: $N$ $Q$ $a_1$ $a_2$ $\dots$ $a_N$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$ Each query is given in one of the following three formats: $1$ $L$ $R$ $x$ $2$ $L$ $R$ $y$ $3$ $L$ $R$ [samples]

Samples

Input #1

Output #1

13
4
9

Initially, $A = (2, 5, 6)$. Thus, the answer to the $1$\-st query is $a_1 + a_2 + a_3 = 2 + 5 + 6 = 13$.  
When the $2$\-nd query has been processed, $A = (2, 2, 3)$. Thus, the answer to the $3$\-rd query is $a_1 + a_2 = 2 + 2 = 4$.  
When the $4$\-th query has been processed, $A = (3, 3, 3)$. Thus, the answer to the $5$\-th query is $a_1 + a_2 + a_3 = 3 + 3 + 3 = 9$.

Input #2

6 11
10 3 5 20 6 7
3 1 6
1 2 4 3
3 1 3
2 1 4 10
3 3 6
1 3 6 2
2 1 4 5
3 1 6
2 1 3 100
1 2 5 6
3 1 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Ex - I like Query Problem",
    "description": {
      "content": "You are given $N$, $Q$, and $A=(a_1,\\ldots,a_N)$.   Process $Q$ queries described below. Each query is of one of the following three kinds: *   `1 L R x`: for $i=L,L+1,\\dots,R$, update the value of $",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc256_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given $N$, $Q$, and $A=(a_1,\\ldots,a_N)$.  \nProcess $Q$ queries described below. Each query is of one of the following three kinds:\n\n*   `1 L R x`: for $i=L,L+1,\\dots,R$, update the value of $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments