原题链接：https://loj.ac/p/6913
变态扫描线。
形式化题意
给出 k 行 n 列的矩阵 (ai,j)1≤i≤k,1≤j≤n，对 q 个询问，每次询问给出 l,r，求：
$$\sum_{l\leq x\leq y\leq r}F\bigg(\max_{1\leq i\leq k}\min_{x\leq j\leq y}a_{i,j}\bigg)
$$其中 F(x)=A⊕(Bx+C)。
做法
显然这个 F 的意思就是防止你把里面的东西拆到外面，我们套路地考虑哪些子区间的 F 是一样的。
对于同一行，满足 minx≤j≤yai,j=ai,p,x≤p≤y 的 x,y 显然是在 p 两边且覆盖两段连续段，这里就有一个天才的想法：对所有 ai,j 从大到小排序并顺序加入。如果 ai,j−1 和 ai,j+1 之前加入过，那么 x,y 就可以在两边连续段分别进行取值，然后由 p 合并成一个新的连续段，这只需要并查集简单维护即可。
从大到小加入的另一个好处是，它的顺序也使得外层 max 更好处理。我们不妨再思考套路，子区间问题映射到二维平面通常是一种不错的视角，具体的，我们设横轴为 l，纵轴为 r，设对于 p 使得 minx≤j≤yai,j=ai,p 满足 x∈[Lp,p],y∈[p,Rp] ，则 x,y 的合法取值映射到二维空间就是一个 [Lp,p]×[p,Rp] 的矩形，而这个 max 制约了我们后加入的矩形不能覆盖之前的矩形。
听起来并不好处理，因为矩形之间可能会有重叠，那怎么办？
考虑什么东西是好维护的。如果我们可以把这些矩形变成阶梯状，将易于维护（要不然难以把后加入的矩形进行切割）。不如大胆将矩形向右下角扩张，即变成 [Lp,n]×[1,Rp]，它包含了三个部分，第一部分是原来合法的部分，第二部分是 y=x 合法线以下的部分（l>r 不合法，值为 0），而第三部分是合法的，比如 [p+1,Rp]。但你仔细观察：第三部分一定被之前加入过的连续段完全覆盖！也就是说它一定被之前加入的矩形覆盖了，我们不用管它。那么后加入矩形剩下要加入的部分，都位于阶梯之上，原阶梯每一个顶点都会对这个矩形切一刀，而顶点数显然是 O(n) 的（每个矩形最多贡献一个顶点），维护阶梯每一段的高然后遍历加入矩形再推平，复杂度是对的（珂朵莉树是好东西）。
下图蓝色矩形是旧阶梯，红色矩形是新加入的矩形。
每个矩形（三角形）的贡献为 面积×F(ai,p)，面积怎么算？考虑使用特殊的线段树进行扫描线。自下而上扫描的时候，我们线段树维护两个和 [sum,hsum]，sum 不考虑合法线阶段，对矩形做普通扫描线。每扫完新的一行把 y=x 左边所有区间的 hsum+=sum，询问的时候查询这个 hsum。这个操作叫做 tick。
这个操作是有时间顺序的，怎么下传懒标记？
利用矩阵天然的结合律性质，我们设向量 [hsum′,sum′,len′]，其中 len 是区间长度，而之前的向量为 [hsum,sum,len]，则 tick 操作的矩阵：
$$[hsum',sum',len']=[hsum,sum,len]\times
\begin{bmatrix}
1&0&0\\
1&1&0\\
0&0&1
\end{bmatrix}
$$为了保证顺序加法也需要用矩阵表示，假设我们要区间加 V：
$$[hsum',sum',len']=[hsum,sum,len]\times
\begin{bmatrix}
1&0&0\\
0&1&0\\
0&V&1
\end{bmatrix}
$$当然嫌常数大也可以手动展开矩阵乘法删掉那些永远是 0 的项。
我的稀疏矩阵乘法线段树是 gemini 写的，我实在懒得写这个了。。。这个题太长。。。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug cout<<"debug"<<endl;
#define MOD (1000000007)
using namespace std;
const int MAXN = 5e4 + 10;
int k, n, q, a[MAXN][21], A, B, C;
pair<int, pair<int, int>> rk[MAXN * 20];
int rk_idx;
struct DSU {
int fa[MAXN], l[MAXN], r[MAXN];
inline int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
inline void init() {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
l[i] = r[i] = i;
}
}
inline void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
fa[fx] = fy;
l[fy] = min(l[fy], l[fx]);
r[fy] = max(r[fy], r[fx]);
}
}
};
struct ODT {
struct Area {
int l, r;
mutable int v;
Area(int vl, int vr, int vv) {
l = vl, r = vr, v = vv;
}
bool operator<(const Area& other)const {
return l < other.l;
}
};
set<Area> tr;
set<Area>::iterator split(int pos) {
set<Area>::iterator it = tr.lower_bound(Area(pos, 0, 0));
if (it != tr.end() && pos == it->l) return it;
--it;
if (it->r < pos) return tr.end();
int l = it->l, r = it->r, v = it->v;
tr.erase(it);
tr.emplace(l, pos - 1, v);
return tr.emplace(pos, r, v).first;
}
};
struct Segment {
int p, l, r, v;
Segment() {}
Segment(int _p, int _l, int _r, int _v): p(_p), l(_l), r(_r), v(_v) {}
bool operator<(const Segment&other) const {
return (p == other.p) ? v < other.v : p < other.p; //开区间写法，先处理删除矩形
}
};
// 1. 定义矩阵乘法运算（只展开非 0 项，常数极小）
struct matrix {
int mat[3][3];
matrix() {
memset(mat, 0, sizeof(mat));
}
// 初始化为单位矩阵
inline void identity() {
memset(mat, 0, sizeof(mat));
mat[0][0] = mat[1][1] = mat[2][2] = 1;
}
// 矩阵相乘（直接白嫖 std 的展开公式）
friend matrix operator * (const matrix A, const matrix B) {
matrix C;
C.mat[0][0] = 1;
C.mat[1][0] = A.mat[1][0] + B.mat[1][0];
C.mat[1][1] = 1;
C.mat[2][0] = A.mat[2][0] + A.mat[2][1] * B.mat[1][0] + B.mat[2][0];
C.mat[2][1] = A.mat[2][1] + B.mat[2][1];
C.mat[2][2] = 1;
return C;
}
};
司马只因锥 2026-7-29 17:33:59
