[语言月赛202303] M Function G

Luogu

IDLGB3725

Time1000ms

Memory512MB

DifficultyP1

2023O2优化函数与递归语言月赛

对于一个长度为 $n$ 的正整数数列 $a$，Farmer John 定义 M 函数 $M(l, r)$ 如下： $$ M(l, r) = \begin{cases} \left(M(l, \left \lfloor \dfrac{l + r}{2} \right \rfloor) \bmod \max(M(\left \lfloor \dfrac{l + r}{2} \right \rfloor + 1, r), 7)\right ) + \left(a _ {\left \lfloor \frac{l + r}{2} \right \rfloor} - 1 \right ) & |r - l| > 5 \\ \max \limits _ {l \leq i \leq r}{a _ i} & |r - l| \leq 5 \end{cases} $$ $\max \limits _ {l \leq i \leq r}{a _ i}$ 代表 $a _ l, a _ {l + 1}, \cdots, a _ {r - 1}, a _ r$ 中的最大值。 $\left \lfloor x \right \rfloor$ 代表 $\leq x$ 的最大整数。比如 $\left \lfloor 4.2 \right \rfloor = 4$，$\left \lfloor 5 \right \rfloor = 5$。 $\max(x, y)$ 代表 $x, y$ 中的最大值。现在给定 $n$ 和 $a$，请你求出 $M(1, n)$。 ## Input 输入共两行。第一行为一个整数 $n$。第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，对应题目中的正整数数列 $a$。 ## Output 输出共一行一个整数，代表 $M(1, n)$ 的值。 [samples] ## Note ### 样例 1 解释我们这里暂时使用 $\max \{a _ l, a _ {l + 1}, \cdots, a _ r\}$ 来表示 $a _ l, a _ {l + 1}, \cdots, a _ r$ 中的最大值。 $$\begin{aligned} M(1, 10) &= M(1, 5) \bmod \max(M(6, 10), 7) + (a _ 5 - 1) \\ &= \max \{a _ 1, a _ 2 \cdots, a _ 5\} \bmod \max(\max \{a _ 6, a _ 7 \cdots, a _ {10}\}, 7) + (a _ 5 - 1) \\ &= \max \{a _ 1, a _ 2 \cdots, a _ 5\} \bmod \max(84, 7) + (a _ 5 - 1) \\ &= \max \{a _ 1, a _ 2 \cdots, a _ 5\} \bmod 84 + (a _ 5 - 1) \\ &= 91 \bmod 84 + (a _ 5 - 1) \\ &= 7 + (a _ 5 - 1) \\ &= 11 \end{aligned}$$ ### 数据规模与约定对于 $100\%$ 的数据，保证 $1 \leq n \leq 5 \times 10 ^ 5$，$1 \leq a _ i \leq 10 ^ 9$。 | 测试点编号 | $n$ | $a _ i$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1 \sim 2$ | $\leq 10$ | $\leq 100$ | 无 | | $3 \sim 5$ | $\leq 10 ^ 3$ | $\leq 10 ^ 4$ | 无 | | $6$ | $\leq 5 \times 10 ^ 5$ | $\leq 10 ^ 9$ | $a _ i = 1$ | | $7$ | $= 5$ | $\leq 10 ^ 9$ | 无 | | $8 \sim 10$ | $\leq 5 \times 10 ^ 5$ | $\leq 10 ^ 9$ | 无 |

Samples

Input #1

10
3 72 26 91 5 84 18 29 50 23

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛202303] M Function G",
    "description": {
      "content": "对于一个长度为 $n$ 的正整数数列 $a$，Farmer John 定义 M 函数 $M(l, r)$ 如下： $$ M(l, r) = \\begin{cases} \\left(M(l, \\left \\lfloor \\dfrac{l + r}{2} \\right \\rfloor) \\bmod \\max(M(\\left \\lfloor \\dfrac{l + r}{2} \\right \\rfloo",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3725"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对于一个长度为 $n$ 的正整数数列 $a$，Farmer John 定义 M 函数 $M(l, r)$ 如下：\n\n$$\nM(l, r) = \\begin{cases}\n\\left(M(l, \\left \\lfloor \\dfrac{l + r}{2} \\right \\rfloor) \\bmod \\max(M(\\left \\lfloor \\dfrac{l + r}{2} \\right \\rfloo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments