原题链接：https://loj.ac/p/6913

变态扫描线。

形式化题意

给出 $k$ 行 $n$ 列的矩阵 $(a_{i,j})_{1\leq i\leq k,1\leq j\leq 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\oplus(Bx+C)$。

做法

显然这个 $F$ 的意思就是防止你把里面的东西拆到外面，我们套路地考虑哪些子区间的 $F$ 是一样的。

对于同一行，满足 $\min_{x\leq j\leq y}a_{i,j}=a_{i,p},x\leq p\leq y$ 的 $x,y$ 显然是在 $p$ 两边且覆盖两段连续段，这里就有一个天才的想法：对所有 $a_{i,j}$ 从大到小排序并顺序加入。如果 $a_{i,j-1}$ 和 $a_{i,j+1}$ 之前加入过，那么 $x,y$ 就可以在两边连续段分别进行取值，然后由 $p$ 合并成一个新的连续段，这只需要并查集简单维护即可。

从大到小加入的另一个好处是，它的顺序也使得外层 $\max$ 更好处理。我们不妨再思考套路，子区间问题映射到二维平面通常是一种不错的视角，具体的，我们设横轴为 $l$，纵轴为 $r$，设对于 $p$ 使得 $\min_{x\leq j\leq y}a_{i,j}=a_{i,p}$ 满足 $x\in[L_p,p],y\in [p,R_p]$ ，则 $x,y$ 的合法取值映射到二维空间就是一个 $[L_p,p]\times [p,R_p]$ 的矩形，而这个 $\max$ 制约了我们后加入的矩形不能覆盖之前的矩形。

听起来并不好处理，因为矩形之间可能会有重叠，那怎么办？

考虑什么东西是好维护的。如果我们可以把这些矩形变成阶梯状，将易于维护（要不然难以把后加入的矩形进行切割）。不如大胆将矩形向右下角扩张，即变成 $[L_p,n]\times [1,R_p]$，它包含了三个部分，第一部分是原来合法的部分，第二部分是 $y=x$ 合法线以下的部分（$l>r$ 不合法，值为 $0$），而第三部分是合法的，比如 $[p+1,R_p]$。但你仔细观察：第三部分一定被之前加入过的连续段完全覆盖！也就是说它一定被之前加入的矩形覆盖了，我们不用管它。那么后加入矩形剩下要加入的部分，都位于阶梯之上，原阶梯每一个顶点都会对这个矩形切一刀，而顶点数显然是 $O(n)$​ 的（每个矩形最多贡献一个顶点），维护阶梯每一段的高然后遍历加入矩形再推平，复杂度是对的（珂朵莉树是好东西）。

下图蓝色矩形是旧阶梯，红色矩形是新加入的矩形。

每个矩形（三角形）的贡献为 $面积\times F(a_{i,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;
	}
};

// 2. 矩阵乘法线段树
struct Segment_Tree {
#define lc (p<<1)
#define rc (p<<1|1)
	struct Node {
		int f[3];      // f[0]: sumh(历史和), f[1]: sum(当前值), f[2]: len(长度)
		matrix mat;    // 懒惰标记矩阵
		bool tag;      // 标记是否有效
	} tr[MAXN << 2];

	inline void push_up(int p) {
		tr[p].f[0] = tr[lc].f[0] + tr[rc].f[0];
		tr[p].f[1] = tr[lc].f[1] + tr[rc].f[1];
		tr[p].f[2] = tr[lc].f[2] + tr[rc].f[2];
	}

	// 初始化，必须先调用，为了给 f[2] (长度) 赋初始值 1
	void build(int p, int l, int r) {
		tr[p].tag = false;
		tr[p].mat.identity();
		tr[p].f[0] = tr[p].f[1] = 0;
		if (l == r) {
			tr[p].f[2] = 1; // 初始化底层的区间长度
			return;
		}
		int mid = (l + r) >> 1;
		build(lc, l, mid);
		build(rc, mid + 1, r);
		push_up(p);
	}

	// 把矩阵 A 乘到节点 p 上
	inline void Assign(int p, const matrix& A) {
		int g[3] = {0};
		g[0] = tr[p].f[0] + tr[p].f[1] * A.mat[1][0] + tr[p].f[2] * A.mat[2][0];
		g[1] = tr[p].f[1] + tr[p].f[2] * A.mat[2][1];
		g[2] = tr[p].f[2];

		tr[p].f[0] = g[0], tr[p].f[1] = g[1], tr[p].f[2] = g[2];

		// 标记下传合并：新标记 = 老标记 * 新来的矩阵 A
		if (!tr[p].tag) {
			tr[p].tag = true;
			tr[p].mat = A;
		} else {
			tr[p].mat = tr[p].mat * A;
		}
	}

	inline void push_down(int p) {
		if (tr[p].tag) {
			Assign(lc, tr[p].mat);
			Assign(rc, tr[p].mat);
			tr[p].tag = false;
			tr[p].mat.identity(); // 恢复为单位矩阵
		}
	}

	// 执行加法操作：乘上 M_{add}
	void update_add(int p, int l, int r, int L, int R, int V) {
		if (l >= L && r <= R) {
			matrix A;
			A.identity();
			A.mat[2][1] = V; // 在 (2,1) 放置要加的值
			Assign(p, A);
			return;
		}
		push_down(p);
		int mid = (l + r) >> 1;
		if (L <= mid) update_add(lc, l, mid, L, R, V);
		if (R > mid) update_add(rc, mid + 1, r, L, R, V);
		push_up(p);
	}

	// 执行历史累加：乘上 M_{tick}
	void update_tick(int p, int l, int r, int L, int R) {
		if (L > R) return;
		if (l >= L && r <= R) {
			matrix A;
			A.identity();
			A.mat[1][0] = 1; // 触发一次 Tick
			Assign(p, A);
			return;
		}
		push_down(p);
		int mid = (l + r) >> 1;
		if (L <= mid) update_tick(lc, l, mid, L, R);
		if (R > mid) update_tick(rc, mid + 1, r, L, R);
		push_up(p);
	}

	// 查询区间历史和
	int query_hsum(int p, int l, int r, int L, int R) {
		if (l >= L && r <= R) return tr[p].f[0]; // f[0] 就是我们要的 Ans
		push_down(p);
		int mid = (l + r) >> 1, res = 0;
		if (L <= mid) res += query_hsum(lc, l, mid, L, R);
		if (R > mid) res += query_hsum(rc, mid + 1, r, L, R);
		return res;
	}
#undef lc
#undef rc
};
DSU dsu[21];
bitset<MAXN> tag[21];
ODT odt;
vector<Segment> seg;
vector<int> modify[MAXN], query[MAXN];
pair<int, int> que[MAXN];
Segment_Tree st;
int ans[MAXN];
inline int F(int x) {
	return A ^ (B * x + C);
}
inline void add_square(int l1, int r1, int l2, int r2, int d) {
	auto itr = odt.split(r1 + 1), itl = odt.split(l1), it = itl; //珂朵莉树维护上轮廓线,itr其实没必要，但我是复制的板子
	for (; it != itr; ++it) { //左上顶点只有O(kn)个，遍历odt复杂度是对的
		if (it->v >= r2) break ;
		seg.emplace_back(it->v + 1, it->l, it->r, d);
		seg.emplace_back(r2 + 1, it->l, it->r, -d);
	}
	if (it == itl) return ;
	int l = l1, r = prev(it)->r;
	if (l <= r) {
		odt.tr.erase(itl, it);
		odt.tr.emplace(l, r, r2);
	}
	return ;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> k >> n >> q;
	for (int i = 1; i <= k; ++i) dsu[i].init();
	for (int i = 1; i <= k; ++i) {
		for (int j = 1; j <= n; ++j) {
			cin >> a[j][i];
			rk[++rk_idx] = {a[j][i], {i, j}};
		}
	}
	cin >> A >> B >> C;
	sort(rk + 1, rk + rk_idx + 1, greater<pair<int, pair<int, int>>>());
	odt.tr.emplace(1, n, 0);
	for (int p = 1; p <= rk_idx; ++p) {
		auto [i, j] = rk[p].second;
		tag[i][j] = true;
		if (tag[i][j - 1]) dsu[i].merge(j, j - 1);
		if (tag[i][j + 1]) dsu[i].merge(j, j + 1);
		int root = dsu[i].find(j);
		int L = dsu[i].l[root];
		int R = dsu[i].r[root];
		add_square(L, n, 1, R, F(rk[p].first));
	}
	for (int i = 0; i < seg.size(); ++i) { //给线段桶排
		modify[seg[i].p].emplace_back(i);
	}
	for (int i = 1; i <= q; ++i) {
		cin >> que[i].first >> que[i].second;
		query[que[i].second].emplace_back(i);
	}
	st.build(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		for (int idx : modify[i]) {
			st.update_add(1, 1, n, seg[idx].l, seg[idx].r, seg[idx].v);
		}
		st.update_tick(1, 1, n, 1, i);
		for (int idx : query[i]) {
			ans[idx] = st.query_hsum(1, 1, n, que[idx].first, n);
		}
	}
	for (int i = 1; i <= q; ++i) cout << ans[i] << endl;
	return 0;
}