『STA - R5』ReLyna

Luogu

IDLGP10399

Time5000ms

Memory512MB

DifficultyP6

O2优化

你手中有一个数字 $x$。走到位置 $i$ 时你可以将手中的数字变为 $x+a_i$ 或 $x\times b_i$。有 $m$ 次操作。 - `1 x y z`，执行 $a_x\gets y$，$b_x\gets z$。 - `2 l r`，查询若你从 $[l,r]$ 的所有子区间中等概率选择一个子区间 $[l',r']$，则你从 $l'$ 走到 $r'$ 后手中的数的最大值的期望是多少？答案对 $10^9+7$ 取模。每次行动开始前你手中的数字都会归零。如果你不知道有理数如何取模，可以参考 [P2613 有理数取余](https://www.luogu.com.cn/problem/P2613)。可参考样例解释理解题意。 ## Input 第一行两个整数 $n,m$。第二行 $n$ 个整数，第 $i$ 个整数代表 $a_i$。第三行 $n$ 个整数，第 $i$ 个整数代表 $b_i$。后 $m$ 行每行描述一次操作，格式见题目描述。 ## Output 对于每个询问，输出对应的期望。答案对 $10^9+7$ 取模。 [samples] ## Background ![](https://pic.imgdb.cn/item/661a29dd68eb93571321ac89.webp) ## Note **样例解释** 对于第一次询问，令 $f(i,j)$ 为你从 $i$ 开始顺次走到 $j$ 后手中的数的最大值，则答案为 $\frac{1}{3}[f(2,2)+f(2,3)+f(3,3)]=\frac{1}{3}(52+156+8)=72$。 **数据范围** | 子任务编号 | $n$ | $m$ | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | Subtask #1 | $50$ | $50$ | 无 | 5 | | Subtask #2 | $500$ | $500$ | 无 | 5 | | Subtask #3 | $10^5$ | $10^5$ | 保证任何时刻 $a_i=1$ | 25 | | Subtask #4 | $10^5$ | $50$ | 无 | 25 | | Subtask #5 | $10^5$ | $10^5$ | 没有修改操作 | 25 | | Subtask #6 | $10^5$ | $10^5$ | 无 | 15 | 对于所有数据，$1\le n,m\le 10^5$，$0<a_i<10^9+7$，$1<b_i<10^9+7$，保证操作合法，保证所有输入均为整数。

Samples

Input #1

5 4
48 52 8 27 34 
3 4 3 2 2 
2 2 3
2 1 5
1 1 34 4
2 1 3

Output #1

72
133333711
333333468

API Response (JSON)

{
  "problem": {
    "name": "『STA - R5』ReLyna",
    "description": {
      "content": "你手中有一个数字 $x$。走到位置 $i$ 时你可以将手中的数字变为 $x+a_i$ 或 $x\\times b_i$。 有 $m$ 次操作。 - `1 x y z`，执行 $a_x\\gets y$，$b_x\\gets z$。 - `2 l r`，查询若你从 $[l,r]$ 的所有子区间中等概率选择一个子区间 $[l',r']$，则你从 $l'$ 走到 $r'$ 后手中的数的最大值的期望是多少",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10399"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你手中有一个数字 $x$。走到位置 $i$ 时你可以将手中的数字变为 $x+a_i$ 或 $x\\times b_i$。\n\n有 $m$ 次操作。\n\n- `1 x y z`，执行 $a_x\\gets y$，$b_x\\gets z$。\n\n- `2 l r`，查询若你从 $[l,r]$ 的所有子区间中等概率选择一个子区间 $[l',r']$，则你从 $l'$ 走到 $r'$ 后手中的数的最大值的期望是多少...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments