Magenta Potion

Luogu

IDLGP8563

Time1000ms

Memory128MB

DifficultyP4

线段树二分洛谷原创O2优化洛谷月赛

给定一个长为 $n$ 的整数序列 $a$，其中所有数的绝对值均大于等于 $2$。有 $q$ 次操作，格式如下： $\texttt{1 i k}$，表示将 $a_i$ 修改为 $k$。保证 $k $ 的绝对值大于等于 $2$。 $\texttt{2 l r}$，考虑 $[l,r]$ 的子区间（包括本身）中乘积最大的的区间乘积 $M$。如果 $M>2^{30}$，输出 `Too large`，否则输出 $M$。特别地，空区间的元素乘积定义为 $1$。 ## Input 第一行两个正整数表示 $n,q$。第二行输入 $n$ 个**整数**表示 $a_i$。接下来 $q$ 行，每行三个整数表示一次询问，格式见上。 ## Output 对于每次 $\tt2$ 操作输出一行表示询问的答案。 [samples] ## Note 对于所有的数据，$2\le |a_i|,|k| \le 10^9$，$1 \le n,q \le 2\times 10^5$，$1 \le l \le r \le n$。 $$ \def\arraystretch{1.5} \begin{array}{c|c|c}\hline \textbf{测试点编号}&\bm{~~~~~~~~n,q\le~~~~~~~~}&~~~~\textbf{特殊限制}~~~~\cr\hline \textsf1\sim \sf2 & 10& \cr\hline \sf3\sim 6 & 100& \cr\hline \sf7\sim 10 & 5 \times 10^3&\cr\hline \sf 11\sim 13 & &\sf A\cr\hline \sf14\sim 16 & & \sf B\cr\hline \sf17\sim 20 & &\cr\hline \end{array} $$ $\textsf A$：保证 $a_i,k \ge 2$。 $\textsf B$：保证对于每一组询问，对应的 $r-l \ge 100$。

Samples

Input #1

Output #1

240
20
1
Too large

API Response (JSON)

{
  "problem": {
    "name": "Magenta Potion",
    "description": {
      "content": "给定一个长为 $n$ 的整数序列 $a$，其中所有数的绝对值均大于等于 $2$。有 $q$ 次操作，格式如下： $\\texttt{1 i k}$，表示将 $a_i$ 修改为 $k$。保证 $k $ 的绝对值大于等于 $2$。 $\\texttt{2 l r}$，考虑 $[l,r]$ 的子区间（包括本身）中乘积最大的的区间乘积 $M$。如果 $M>2^{30}$，输出 `Too large`，否则",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8563"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长为 $n$ 的整数序列 $a$，其中所有数的绝对值均大于等于 $2$。有 $q$ 次操作，格式如下：\n\n$\\texttt{1 i k}$，表示将 $a_i$ 修改为 $k$。保证 $k $ 的绝对值大于等于 $2$。\n\n$\\texttt{2 l r}$，考虑 $[l,r]$ 的子区间（包括本身）中乘积最大的的区间乘积 $M$。如果 $M>2^{30}$，输出 `Too large`，否则...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments