$n\le 100$

对于询问 $[l,r]$，暴力枚举 $l',r'$，然后暴力计算，时间复杂度为 $O(mn^3)$。

或者简单优化一下到 $O(mn^2)$。期望得分 $10$。

$n\le 1000$

先预处理出所有区间的权值 $v_{l,r}$。

然后可以用各种做法求出所有区间的子区间的权值 $ans_{l,r}$。

时间复杂度为 $O(n^2+m)$。期望得分 $30$。

特殊性质

按位与，按位或，$\gcd$ 三种运算有一个很厉害的性质，以 $\gcd$ 为例：对于一个数 $x$，不断令 $x\gets \gcd(x,v)$，则 $x$ 值发生变化的次数为 $\log V$ 次。

具体的原因可以均摊分析，考虑 $x$ 的质因子可重集合，显然其大小不超过 $\log V$，每次取 $\gcd$，这个集合要么不变，要么大小至少减一，只有集合大小改变才会影响 $x$ 的值，所以 $x$ 值发生变化的次数为 $\log V$ 次。

按位与和按位或也是如此，每一位上只会从一种值变成另一种值，所以变化次数也不超过 $\log V$。

数据随机后，若一个区间长度超过 $100$，答案就极有可能变成 $0$ 了。

然后乱搞一下应该可以得到 $40$ 的分数。

$n\le 10^5$

考虑离线扫描线。

有这样一种经典扫描方式，令 $r:1\to n$，假设当前扫到 $r$，我们让 $\forall l \in [1,r]$ 的位置 $v_l$ 加上区间 $[l,r]$ 的权值。

这样若对于询问 $[L,R]$，若 $r$ 扫到了 $R$，则查询 $v_{L\sim R}$ 的区间和即可。这是非常经典的增量贡献求答案的方法。

回到本题，使用上面所述的扫描线算法，因为上述特殊性质的存在，假设当前扫到 $r$，设 $A_i$ 为 $i\sim r$ 的区间按位与的和，$B_i,C_i$ 同理，则这三个数组分别可以划分为 $\log V$ 段，每一段内值相同。

这样我们得到 $3\log V$ 断点，设 $D_i=A_iB_iC_i$。则 $D_i$ 也被划分成 $\log V$ 段，每一段内部值相同。

那么我们令 $\forall i\in [1,r],v_i\gets v_i+D_i$，这样更新过程可以转化成对 $v$ 数组的 $\log V$ 段区间加法。

查询答案即为查询区间和，找断点可以二分加线段树，总而言之时间复杂度为 $O(n\log^2 n+m\log n)$，期望得分 $80$。

如果你用下文所述找断点的方法，用树状数组常数小的话也可以得到 $100$。

$n\le 5\times 10^5,m\le 5\times 10^6$

考虑正解，静态询问，且 $q\le 5\times 10^6$，应该要做到 $O(1)$ 回答询问，考虑离线扫描线。

有这样一种不经典的扫描线方法：维护一个指针 $r$ 从 $1$ 扫到 $n$，每扫到一个位置就回答右端点在 $r$ 的询问的答案。考虑此时在第 $l$ 个位置上维护 $w_{r,l}$ 表示 $[l,r]$ 所有子区间的价值之和。

不难发现我们把题目又读了一遍。考虑当 $r-1\to r$ 时，$w_{r,l}$ 相比于 $w_{r-1,l}$ 的答案应该有怎样的变化。

注意 $w_{r,l}$ 的理解，可以理解成当指针扫到 $r$ 时的版本时，第 $l$ 个位置的值，并不需要真正维护二维数组，只需要滚动维护第二维即可，下文同样有类似的表达方法。

令 $A_{r,i}$ 表示扫到 $r$ 时 $i\sim r$ 的所有数按位与之和，$B_{r,i},C_{r,i}$ 同理，则需要更新：

$$w_{r,i}\gets w_{r-1,i}+\sum_{j=i}^rA_{r,j}B_{r,j}C_{r,j}$$

先考虑如何维护 $A_{r,i},B_{r,i},C_{r,i}$。不难发现，当 $r\to r+1$ 时，发生更改的 $A_{r,i},B_{r,i},C_{r,i}$ 都是 $1\sim r$ 的一段后缀。

对于 $x<y$，若 $C_{r+1,y}=\gcd(C_{r,y},c_{r+1})=C_{r,y}$，则显然有 $C_{r+1,x}=\gcd(C_{r,x},c_{r+1})=C_{r,x}$，因为 $C_{r,x},C_{r,y}$ 和 $C_{r,y},c_{r+1}$ 在集合上都是子集关系。

当 $r\to r+1$考虑这样一种更新方式，从 $r$ 出发，用 $r+1$ 的值倒着更新 $r-1,r-2,\dots$ 的位置，直到 $A_{r,i},B_{r,i},C_{r,i}$ 都不发生改变，则更新完成。

分析复杂度，以 $A_{r,i}$ 为例，这个位置对最终复杂度有贡献当且仅当某次更新时 $A_{r,i}$ 发生了改变，根据最上面的分析，这种改变次数是不超过 $\log V$ 的，所以更新的总的复杂度为 $O(n\log V)$。

此时,当 $r-1\to r$ 时，维护一个前缀和 $s_{r,i}$：

$$s_{r,i}=\sum_{j=1}^nA_{r,j}B_{r,j}C_{r,j}$$

则更新可以表示为：

$$w_{r,l}\gets w_{r-1,l}+s_{r,r}-s_{r,l-1}$$

令 $v_i=s_{i,i}$，则有：

$$w_{r,l}=\sum_{i=l}^rv_i-\sum_{i=l}^rs_{i,l-1}$$

前面的部分显然可以单独维护，后边的部分则是查询 $s$ 所有版本在位置 $i$ 上的历史和。

因为我们每次修改都是暴力修改 $s$，所以问题变成：

1. 单点修改某个位置的值 $s_i$。

2. 单点查询某个位置的历史和

这个东西已经非常简洁了，考虑第 $i$ 个位置的历史和 $hs_i$，$s_i$ 上一次修改的时间 $lst_i$，若在时刻 $t$ 修改 $s_i$ 为 $val$，则：

$$hs_i\gets hs_i+(t-lst_i)s_i,s_i\gets val,lst_i\gets t$$

则在 $t$ 时刻查询位置 $i$ 的历史和为：

$$hs_i+(t-lst_i+1)s_i$$

然后我们惊奇的发现这个问题就解决了。

时间复杂度为 $O(n\log n+m)$，期望得分 $100$。

代码实现

首先是 $\gcd$，可以用 C++ 自带的 `__gcd` 函数，也可以手写二进制优化更相减损术的 $\gcd$，两种写法各有优劣。

然后是快读快输，这个题已经卡常到普通的 fread 和 fwrite 已经无法满足了，建议找个又臭又长的封装版快读快输使用。

然后将询问储存：对于储存询问，不建议将左右端点分开两个数组储存，建议直接用结构体或者 pair 来储存询问左右端点（我也不知道为什么啊，可能是寻址更快吧）。

然后是将离线：不要用 vector，可以用链表在端点处挂上询问。不要用 sort，可以用计数排序。

luogu 的原题需要严厉的卡常，这里不知道是否需要。

$n\le 10$

暴搜，时间复杂度 $O(n!m)$，期望得分 $20$。

$n\le 300$

令 $p_u$ 表示 $u$ 的父亲节点。根据 $l_i\le r_i<i$，不难有 $p_u<u$。

设 $u<v$，则 $p_v$ 一定在 $(u,v)$ 的路径上。

考虑证明：若 $p_v$ 不在 $(u,v)$ 路径上，当且仅当 $v$ 时 $u$ 的祖先，根据 $p_u<u$ 可以得到 $u$ 的祖先编号小于 $u$，即 $u>v$，与 $u<v$ 矛盾，故原命题得证。

以上完成本题最为关键的结论证明。

若对于每一次加操作，都暴力完成，复杂度显然是指数级。

不过对于每一种加操作，都可以用 $(u,v)$ 表示（下文均假设 $u<v$）且 $(u,v)$ 的加操作可以转化为 $(u,p_v)$ 的加操作。

若对链 $(a,b)$ 的加操作对链 $(c,d)$ 的加操作有转化，必须满足 $b<d$。且对于 $a\ne b$ 的情况，对链 $(a,c)$ 的加操作和链 $(b,c)$ 的加操作之间不会互相转化。

也就是说，我们以第二维按照 $v$ 划分所有链，可以分成若干层，当前层只会影响这层之前的层，且层内部之间不会影响。

可以设计出一个递推状物，设 $g_{u,v}$ 表示所有操作对 $(u,v)$ 这条链加上的期望值，则有：

$${g_{u,p_v}\gets g_{u,p_v}+\frac{g_{u,v}}{r_v-l_v+1}},  u<p_u  $$

$${g_{p_{v},u} \gets g_{u,p_v}+\frac{g_{u,v}}{r_v-l_v+1}},  u>p_u$$

注意到编码过程中，为了方便讨论，我们始终只对 $u<v$ 的状态操作，因此若出现 $p_v<u$ 的情况，要操作 $g_{p_v,u}$ 而不是 $g_{u,p_v}$。

其实是简单排列组合原理，每一层内部的转移因为无所谓，所以第一维的枚举顺序可以随便来。

递推完所有的 $g_{u,v}$ 后，考虑计算点 $u$ 的答案，根据结论，只要 $v<u$，那么 $(v,u)$ 的路径一定包含 $(p_u,u)$ 这条链，且对于任意 $(a,u),(b,u)$ 之间互不影响，说明 $(a,u),(b,u)$ 代表的加操作独立，可以直接加起来。

因此答案为 $\sum_{v<u}g_{v,u}$。直接做需要枚举每个点的父亲，时间复杂度 $O(n^3+m)$。期望得分 $60$。

$n\le 2000$

考虑优化这个过程，把 $g$ 数组当成一个二维平面，代码中 $k>i$ 的部分实际上是对横着的一段加上了一个数。$k<i$ 的部分是对竖着的一段加上了一个数。

可以用二维差分优化，递推的过程中求差分的前缀和数组，因为要求前缀和，所以第一维的枚举顺序也需要确定。

时间复杂度 $O(n^2+m)$，期望得分 $100$。