题目分析
本题要求处理大量区间查询，计算所有子区间价值之和。直接枚举子区间不可行，需要高效算法。

---

算法思路

核心思想：增量维护 + 历史版本和

关键观察：

• 固定右端点 $r$，考虑所有以 $r$ 结尾的子区间 $[l, r]$
• 当 $r$ 右移时，可以利用之前的结果增量计算

---

算法流程详解

1. 问题转化

对于查询 $[L, R]$，答案为：

$$\sum_{r=L}^R \sum_{l=L}^r f(l, r)$$

其中 $f(l, r) = (\text{AND}_{i=l}^r a_i) \times (\text{OR}_{i=l}^r b_i) \times (\gcd_{i=l}^r c_i)$

2. 增量维护

固定右端点 $r$，维护所有 $f(l, r)$ 的前缀和：

while (ptr) {
    uint w1 = a[ptr] & a[ptr + 1];
    uint w2 = b[ptr] | b[ptr + 1]; 
    uint w3 = __gcd(c[ptr], c[ptr + 1]);
    if (w1 == a[ptr] && w2 == b[ptr] && w3 == c[ptr])
        break;
    a[ptr] = w1; b[ptr] = w2; c[ptr] = w3;
    --ptr;
}

这段代码从右往左合并区间，直到值不再变化，减少需要更新的位置。

3. 历史版本和

使用 p[], q[], t[], T 维护带时间戳的前缀和：

• p[i]: 当前位置的导数（增量）
• q[i]: 基础值
• t[i]: 最后更新时间
• T: 当前时间

更新公式：

q[i] = val(i - 1);  // 继承之前的值
while (ptr <= i) {
    q[ptr] = val(ptr);
    p[ptr] = p[ptr - 1] + a[ptr] * b[ptr] * c[ptr];
    t[ptr] = T;
    ++ptr;
}
++T;

4. 查询处理

rst[x.se] = val(i) - val(x.fi - 1);

利用前缀和性质：$sum[L,R] = prefix[R] - prefix[L-1]$

---

关键技术与优化

1. 区间合并优化

• 利用位运算和gcd的性质，减少重复计算
• 当值不变时提前终止，均摊 $O(1)$

2. 历史版本管理

• 通过时间戳避免重复计算
• 支持快速区间查询

3. 高效IO

• 自定义快读快写
• 批量输出减少系统调用

4. 空间优化

• 离线处理查询，按右端点分组
• 原地更新数组，减少内存占用

---

复杂度分析

• 预处理：均摊 $O(n)$
• 查询处理：$O(n + m)$
• 总复杂度：$O(n + m)$

对于 $n \leq 10^6, m \leq 5\times 10^6$ 完全可行。

---

样例验证

样例输入

5 3
3 3 1 1 1
2 1 3 2 2  
4 5 3 4 4
1 2
2 5
4 5

计算过程

• 右端点1: 子区间[1,1]价值=3×2×4=24
• 右端点2: [1,2]=24, [2,2]=3×1×5=15
• 右端点3: 更新多个区间值
• 最终输出: 48, 63, 24

---

算法优势

1. 理论最优：线性复杂度处理大规模数据
2. 实现精巧：利用数学性质大幅优化
3. 内存友好：原地操作减少空间占用
4. 实用性强：适用于类似区间聚合问题

该算法通过巧妙的增量维护和历史版本管理，高效解决了大规模区间查询问题。