本题关联比赛
EYOI与SBOI开学欢乐赛14th

关于逆元数列的近10条评论(全部评论)
回复 @组撒头屯 : 线段树的话好像单次修改的时间复杂度就是 $O(n \log n)$，不太能过的样子 --------------------------------------------------------------------------- 好吧，看来是方法不对 lihaoze 2022-10-26 07:45 4楼
回复 @组撒头屯 : 没看出来这可以直接分块 qwq，用珂朵莉树，每隔一段时间重构一次，时间复杂度不太行（算了下大概是 $\mathcal O(n\sqrt{m}\log{\sqrt{m}})$ 的样子），而且因为我懒，实现得常数很大，如果常数小点或许（？不开 O2 也能过 upd：看来是我查询的时候也把块拆开导致了不必要的重构，把查询改成暴力，重构时间拉长点就能过了 yrtiop 2022-10-25 08:28 3楼
回复 @Skylake : 实际上线段树应该也是可行的，但是竟然没人写 op_组撒头屯 2022-10-24 22:55 2楼
@Skylake ，所以你写了个珂朵莉树?! op_组撒头屯 2022-10-24 22:48 1楼

3738. 逆元数列

★★ 输入文件：invarray.in 输出文件：invarray.out 简单对比
时间限制：1 s 内存限制：256 MiB

这是一道数据结构题。

给定质数 $p$ ，你需要维护一个长为 $n$ 的数列 $\{a_n\}$ ，有如下两种操作形式：

$1\ l\ r\ $，表示将 $a_l…a_r$ 的所有数变为其模 $p$ 的乘法逆元；

$2\ l\ r\ $，表示查询 $a_l…a_r$ 的和。

若整数 $b,p$ 互质，并且 $b|a$ （b能整除a），则存在一个整数 $x$ ，使得 $a/b≡a*x\ (mod\ p)$，我们称 $x$ 为 $b$ 模 $p$ 的乘法逆元（取模运算的乘法逆元）。

第一行三个整数 $n,m,p$。

第二行 $n$ 个数，表示初始的 $\{a_n\}$。

接下来 $m$ 行，每行三个整数 $opt,l,r$ ,表示一次操作，含义如上。 $opt∈\{1,2\}\ ,\ 1≤l≤r≤n$。

若干行，对于每一个操作$2$，输出查询的值。

输入输出样例2

初始： $\{1,2,3,4\}$

第一次操作后：$\{1,3,2,4\}$

对于 $20\%$ 数据，$1≤n,m≤10^2$；

对于 $40\%$ 数据，$1≤n,m≤10^3$；

对于 $100\%$ 数据，$1≤n,m≤10^5，p≤10^9+7\ ,\ 1≤a_i<p$;

$rsr$