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⊕(BxC)F(x)A\oplus(BxC)F(x)A⊕(BxC)。做法显然这个FFF的意思就是防止你把里面的东西拆到外面我们套路地考虑哪些子区间的FFF是一样的。对于同一行满足min⁡x≤j≤yai,jai,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,j1a_{i,j1}ai,j1​之前加入过那么x,yx,yx,y就可以在两边连续段分别进行取值然后由ppp合并成一个新的连续段这只需要并查集简单维护即可。从大到小加入的另一个好处是它的顺序也使得外层max⁡\maxmax更好处理。我们不妨再思考套路子区间问题映射到二维平面通常是一种不错的视角具体的我们设横轴为lll纵轴为rrr设对于ppp使得min⁡x≤j≤yai,jai,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​]它包含了三个部分第一部分是原来合法的部分第二部分是yxyxyx合法线以下的部分lrlrlr不合法值为000而第三部分是合法的比如[p1,Rp][p1,R_p][p1,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不考虑合法线阶段对矩形做普通扫描线。每扫完新的一行把yxyxyx左边所有区间的hsumsumhsumsumhsumsum询问的时候查询这个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} 100\\ 110\\ 001 \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} 100\\ 010\\ 0V1 \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 coutdebugendl; #define MOD (1000000007) using namespace std; const int MAXN 5e4 10; int k, n, q, a[MAXN][21], A, B, C; pairint, pairint, 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; } }; setArea tr; setArea::iterator split(int pos) { setArea::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 Segmentother) 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 (p1) #define rc (p1|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]; bitsetMAXN tag[21]; ODT odt; vectorSegment seg; vectorint modify[MAXN], query[MAXN]; pairint, 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, greaterpairint, pairint, 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; }