LOJ#6913. 树莓立方体自学式题解

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

变态扫描线。

形式化题意

给出kkk行nnn列的矩阵(ai,j)1≤i≤k,1≤j≤n(a_{i,j})_{1\leq i\leq k,1\leq j\leq n}(ai,j​)1≤i≤k,1≤j≤n​，对qqq个询问，每次询问给出l,rl,rl,r，求：
∑l≤x≤y≤rF(max⁡1≤i≤kmin⁡x≤j≤yai,j) \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)l≤x≤y≤r∑​F(1≤i≤kmax​x≤j≤ymin​ai,j​)
其中F(x)=A⊕(Bx+C)F(x)=A\oplus(Bx+C)F(x)=A⊕(Bx+C)。

做法

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

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

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

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

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

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

每个矩形（三角形）的贡献为面积×F(ai,p)面积\times F(a_{i,p})面积×F(ai,p​)，面积怎么算？考虑使用特殊的线段树进行扫描线。自下而上扫描的时候，我们线段树维护两个和[sum,hsum][sum,hsum][sum,hsum]，sumsumsum不考虑合法线阶段，对矩形做普通扫描线。每扫完新的一行把y=xy=xy=x左边所有区间的hsum+=sumhsum+=sumhsum+=sum，询问的时候查询这个hsumhsumhsum。这个操作叫做 tick。

这个操作是有时间顺序的，怎么下传懒标记？

利用矩阵天然的结合律性质，我们设向量[hsum′,sum′,len′][hsum',sum',len'][hsum′,sum′,len′]，其中lenlenlen是区间长度，而之前的向量为[hsum,sum,len][hsum,sum,len][hsum,sum,len]​，则 tick 操作的矩阵：
[hsum′,sum′,len′]=[hsum,sum,len]×[100110001] [hsum',sum',len']=[hsum,sum,len]\times \begin{bmatrix} 1&0&0\\ 1&1&0\\ 0&0&1 \end{bmatrix}[hsum′,sum′,len′]=[hsum,sum,len]×​110​010​001​​
为了保证顺序加法也需要用矩阵表示，假设我们要区间加VVV：
[hsum′,sum′,len′]=[hsum,sum,len]×[1000100V1] [hsum',sum',len']=[hsum,sum,len]\times \begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&V&1 \end{bmatrix}[hsum′,sum′,len′]=[hsum,sum,len]×​100​01V​001​​
当然嫌常数大也可以手动展开矩阵乘法删掉那些永远是000的项。

我的稀疏矩阵乘法线段树是 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; }