题目理解

我们有一个 $k \times n$ 的矩阵 $a$，对于每个区间 $[x, y]$（$x \le y$），定义：

$$M(x, y) = \max_{i=1}^k \left( \min_{j=x}^y a_{i,j} \right) $$

函数 $F(M) = A \oplus (B \cdot M + C)$，其中 $\oplus$ 是按位异或。

对于每个查询 $[l, r]$，需要计算：

$$\sum_{l \le x \le y \le r} F(M(x, y))$$

---

问题分析

核心难点

• 直接枚举所有 $x, y$ 是 $O(n^2)$ 的，不可行
• $M(x, y)$ 是二维的 RMQ 问题：先每行做区间最小值，然后所有行取最大值

关键观察

当固定右端点 $i$，左端点 $j$ 从 $i$ 递减到 $1$ 时，$M(j, i)$ 是单调不增的，并且只会变化 $O(k)$ 次。

这是因为对于每行，$\min_{t=j}^i a_{row,t}$ 关于 $j$ 是单调不增的，而 $M(j,i)$ 是 $k$ 个单调不增函数的 $\max$，所以它的值域变化次数是 $O(k)$。

---

代码解法详解

1. 预处理 ST 表

void make_st() {
    for (int i = 2 ; i <= n ; i ++)
        Lg2[i] = Lg2[i >> 1] + 1 ;

    for (int k = 1 ; k <= K ; k ++) {
        for (int i = 0 ; i <= 16 ; i ++) {
            if (i == 0) {
                for (int j = 1 ; j <= n ; j ++)
                    st[k][i][j] = a[k][j] ;
            } else {
                for (int j = 1 ; j <= n - (1 << i) + 1 ; j ++) {
                    st[k][i][j] = min(st[k][i - 1][j], st[k][i - 1][j + (1 << (i - 1))]) ;
                }
            }
        }
    }
}

为每行建立 RMQ 的 ST 表，用于 $O(1)$ 查询任意区间的行最小值。

2. 单调栈思想 + 二分查找变化点

for (int i = 1 ; i <= n ; i ++) {
    int j = i ;
    for (int tim = 0 ; tim <= 3 * K && j ; tim ++) {
        int v = ask(j, i) ;  // 计算 M(j, i)
        // 二分找到最大的左端点 pos，使得 M(pos, i) = v
        // 那么区间 [ans, j] 的 M(·, i) 都等于 v
        // 用线段树更新这个区间
        change(1, ans, j) ;
        j = ans - 1 ;
    }
}

对于每个右端点 $i$，从 $i$ 开始向左找所有 $M(j, i)$ 的变化点。由于最多只有 $O(k)$ 个变化点，复杂度为 $O(k \log n)$ 每个右端点。

3. 线段树维护区间和

线段树节点存储三个值：

• f[0]：区间内所有 $F(M(x, i))$ 的和
• f[1]：区间长度
• f[2]：常数 1（用于矩阵乘法）

使用矩阵乘法来批量更新区间：

tmp.mat[0][0] = 1, tmp.mat[0][1] = 0, tmp.mat[0][2] = 0 ;
tmp.mat[1][0] = 1, tmp.mat[1][1] = 0, tmp.mat[1][2] = 0 ;
tmp.mat[2][0] = 0, tmp.mat[2][1] = ((v * B + C)^A), tmp.mat[2][2] = 1 ;

这个矩阵的作用是：

• f[0] 保持不变（第一行）
• f[1] 保持不变（第二行）
• f[2] 转换为 F(v) 加到 f[1] 上（第三行）

4. 查询处理

将所有查询按右端点排序，当处理到右端点 $i$ 时，回答所有右端点为 $i$ 的查询：

for (int id : que[i]) {
    ans[id] = query(1, l[id], n) ;
}

---

算法流程

1. 预处理：为每行建立 ST 表
2. 枚举右端点：从 $1$ 到 $n$
   • 使用二分找到所有 $M(j, i)$ 的变化点
   • 用线段树批量更新每个值相同的区间
3. 回答查询：当处理到查询的右端点时，查询线段树得到答案

---

复杂度分析

• 预处理：$O(k n \log n)$
• 主循环：$O(n \cdot k \log n)$（每个右端点 $O(k \log n)$）
• 查询：$O(q \log n)$
• 总复杂度：$O((k n + q) \log n)$，对于 $k \le 20, n,q \le 50000$ 可接受

---

算法标签

• 数据结构
• 线段树
• ST 表 (RMQ)
• 矩阵乘法优化
• 单调栈思想
• 离线查询
• 预处理

---

总结

这道题的解法非常巧妙：

1. 利用单调性：发现 $M(j, i)$ 关于 $j$ 单调且变化点很少
2. 离线处理：按右端点排序查询，逐步构建答案
3. 矩阵批量更新：用矩阵乘法高效更新线段树区间
4. 二分找变化点：快速定位值变化的边界

核心思想是将 $O(n^2)$ 的区间枚举优化到 $O(k n \log n)$，通过充分利用问题的单调性和离线处理技巧，实现了高效求解。