U215418 「MCOI-01 / AC7-M16」 Last Hope

[大样例下载](https://www.luogu.com.cn/problem/U124443) ~~最恶心的一题给了最恶心的一关，毒瘤 M16 /tuu~~

给三个长度为 $n$ 的整数序列 $a,b,c$，$m$ 次询问，每一次给一个序列中的一个区间乘上一个整数，或者给一个区间 $[l,r]$，求满足 $i\in [l,r]$ 的所有关于 $x$ 的方程 $$(a_i\bmod 5015207)x^2+(b_i\bmod 5015207)x+(c_i\bmod 5015207)=0$$ 的所有根（**包括虚根**）的和，分别输出实部模 $5015207$ 的结果和虚部系数模 $5015207$ 的结果。 **$5015207$ 是质数。** **$(x-1)^2=0$ 算作有两个根 $x_1=x_2=1$，但是 $x-1=0$ 算作只有一个根 $x=1$。** 如果有无穷多个根则仅输出 `Infinity`，**保证在不为 `Infinity` 的时候结果在模 $5015207$ 意义下有意义**。

第一行两个整数 $n,m$，分别表示序列长度和操作次数。 第二行 $n$ 个整数，表示序列 $a$。 第三行 $n$ 个整数，表示序列 $b$。 第四行 $n$ 个整数，表示序列 $c$。 接下来 $m$ 行，每行一个操作： - `1 id l r v` - 如果 $id=0$，则将 $a_l, a_{l+1},a_{l+2},\cdots, a_r$ 乘上 $v$； - 如果 $id=1$，则将 $b_l, b_{l+1},b_{l+2},\cdots, b_r$ 乘上 $v$； - 如果 $id=2$，则将 $c_l, c_{l+1},c_{l+2},\cdots, c_r$ 乘上 $v$。 - `2 l r`，表示在 $[l,r]$ 内查询所有上述形式的方程的根的和。

对于每一个 $2$ 操作，输出一行两个整数，用空格分隔，分别表示实部模 $5015207$ 的结果和虚部系数模 $5015207$ 的结果。

**样例说明** 第一次询问操作时，所有方程都是 $x^2+2x+1=0$，根的和为 $-10+0\rm i$，取模之后得到 $5015197$ 和 $0$。 第二次询问操作时，所有方程都是 $2x+1=0$，根的和为 $-\dfrac{5}{2}+0\rm i$，取模之后得到 $2507601$ 和 $0$。 **数据范围与约定** **本题采用捆绑测试。** - Subtask 1（20 pts）：$n,m \le 3 \times 10^3$，时限 1s。 - Subtask 2（10 pts）：$a,b,c,v \ge 1$，无修改操作，时限 5s。 - Subtask 3（15 pts）：无修改操作，时限 5s。 - Subtask 4（15 pts）：$a,b,c,v \ge 1$，时限 5s。 - Subtask 5（40 pts）：无特殊限制，时限 5s。 对于 $100\%$ 的数据，有： - $1\leq n,m\leq 3\times 10^5$； - $0\leq a_i, b_i, c_i, v< 5015207$； - $1\leq l\leq r\leq n$； - $0\leq id\leq 2$。 **本题强制开启 $O2$ 优化。** #### 提示 - 如果您不懂什么是虚根和虚数，请访问 [**OI-Wiki 复数**](https://oi-wiki.org/math/complex/#_1) 或 [**百度百科 虚数**](https://baike.baidu.com/item/%E8%99%9A%E6%95%B0/107344?fr=aladdin) 以了解相关内容。~~现学人教版高中数学 A 版选修 2-2 也行~~ - **读入量较大，请采用适当的读入方式。** #### 说明 Minecraft OI Round 1 B - Idea：ClCN - Solution/Std：ClCN - Data：ClCN - Tester：tarjin