「DROI」Round 2 进制与操作

Luogu
IDLGP9376
Time4000ms
Memory512MB
DifficultyP6
莫队树状数组O2优化可持久化线段树随机化
定义数 $x$ 在 $B$ 进制下的一次操作为以下两种操作中的任意一种: - 令 $x \rightarrow \lfloor \dfrac{x}{B} \rfloor$。 - 令 $x \rightarrow x \times B + t $。其中 $t \in [0,B-1]$。 现给定长度为 $n$ 的序列 $A$。$m$ 次询问,每次询问形如: - `l r B` 表示询问将序列 $A$ 中下标在 $[l,r]$ 之内的数在 $B$ 进制下操作,至少多少次才能将所有数变为相同(注:每次操作是对**一个数**进行操作)。 **询问间相互独立,即操作不会真的进行。** ## Input 第一个两个整数,分别表示 $n,m$。 第二行一行 $n$ 个数,表示序列 $A$。 接下来 $m$ 行,每行三个数,分别表示这次询问的 $l,r,B$。 ## Output 输出共 $m$ 行,其中第 $i$ 行表示第 $i$ 次询问的答案。 [samples] ## Background 与其编写苍白无力的背景,不如出更有质量的题。 ## Note ### 样例解释 对于样例一,五次询问分别将区间内所有数变为 $3$、$4$、$8$、$4$、$6$ 是一种最优操作。 ------------ ### 数据范围 **「本题采用捆绑测试」** - $\operatorname{Subtask} 1(10\%)$:$n,m \leq 1000$。 - $\operatorname{Subtask} 2(20\%)$:保证所有询问 $B=2$。 - $\operatorname{Subtask} 3(40\%)$:$n,m \leq 3 \times 10^4$。 - $\operatorname{Subtask} 4(30\%)$:无特殊限制。 对于 $100\%$ 的数据:$1 \leq n,m \leq 10^5$,$2 \leq A_i,B \leq 10^8$。
Samples
Input #1
5 5
7 6 5 8 9
1 3 2
2 5 2
4 4 6
3 5 4
1 5 3
Output #1
5
8
0
5 
10
Input #2
8 4
10 14 7 11 19 13 7 18 
1 7 4
3 8 2
1 4 4
1 4 2
Output #2
15
18
8
11
API Response (JSON)
{
  "problem": {
    "name": "「DROI」Round 2  进制与操作",
    "description": {
      "content": "定义数 $x$ 在 $B$ 进制下的一次操作为以下两种操作中的任意一种: - 令 $x \\rightarrow \\lfloor \\dfrac{x}{B} \\rfloor$。 - 令 $x \\rightarrow x \\times B + t $。其中 $t \\in [0,B-1]$。 现给定长度为 $n$ 的序列 $A$。$m$ 次询问,每次询问形如: - `l r B` 表示询问将序列 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9376"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "定义数 $x$ 在 $B$ 进制下的一次操作为以下两种操作中的任意一种:\n\n- 令 $x \\rightarrow \\lfloor \\dfrac{x}{B} \\rfloor$。\n\n- 令 $x \\rightarrow x \\times B + t $。其中 $t \\in [0,B-1]$。\n\n现给定长度为 $n$ 的序列 $A$。$m$ 次询问,每次询问形如:\n\n- `l r B` 表示询问将序列 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments