Everyday DS

每日 数据结构。

241201

P11364

考虑一个节点 $u$，和 $u$ 的叶子 $v$ 合并，贡献是若干个连续段对 $[l1,r1]$ 到 $[r1+1,r2]$ 的答案为 $dep_u$。由于 $[l1,r1]$ 内任选两点一定在 $u$ 子树中的某个点被贡献过，所以可以当成 $[l1,r2]$ 有 $dep_u$ 的贡献。对每个 $u$ 维护子树内连续段，启发式合并。因为每个贡献区间都是两个连续段合并起来，所以只有 $n-1$ 个长度 $>1$ 的区间和 $n$ 个单点。

单点可以用 st 表维护区间最大值，对 $k=1$ 的询问贡献。对于有贡献的区间和询问区间，分三类考虑。有贡献的区间左端点小于询问区间左端点，按 $l$ 从小到大扫描线，贡献加在 $r$ 上，查询 $l\le ql,r\in [ql+qk-1,qr]$ 的答案。有贡献的区间右端点大于询问区间右端点同理。否则 $ql\le l\le r\le qr$，按 $r-l+1$ 从大到小扫描线，贡献加在 $l$ 上，查询 $k\ge qk,l\in [ql,qr-qk+1]$ 的答案。

优化启发式合并，只要对每个 $i$ 二分在 $lca(i,i+1)$ 的子树内包含 $i$ 的极长连通块，st 表求区间 dfn 最大最小的点，$O(n\log n)-O(1)$ lca。

241203

CF2041J

令 $c_i=b_i-1$，枚举最大值位置 $l$，令 $a'_i=\min_{i\le j\le l} a_j$，要求 $c_i<a_i$。令 $p_i$ 为最大的 $c_{p_i}<a_i$，要求 $|\{p_i\le v\}|\le v$。维护 $v-\sum [p_i\le v]$ 的最小值和最小值个数，维护 $l$ 两侧的单调栈。合法的 $l$ 的 $\min v-\sum [cp_i\le v]\ge 0$，需要减 $1$ 的 $b_i$ 数量为 $v-\sum [bp_i\le v]=-1$ 的数量。

241204

CF1500E

求 $[sum_i,sum_n-sunm_{n-i}]$ 的并的长度。关于 $\frac{n}{2}$ 对称，两端无交，中间有交，二分。线段树维护区间个数，区间和，区间和的前缀和。

241205

P7028

分块，维护块内的最大前缀和。形如 $v1_ix+v2_iy$，建 $(v2_i,v1_i)$ 的凸包，二分斜率 $\frac{y}{x}$。

241206

Q967

每个线段树节点开 set 维护 $y$ 行的白格对列答案的影响。删掉一个未被染黑的区间时，在被询问区间完全包含的线段树节点删掉 $y$ 的标记，否则下传。线段树维护答案为左右儿子的较大值和当前节点的最小标记的 min。对每个 $y$ set 维护连续段，保证每次删的区间无交。

241208

CF1178G

分块，维护正负的最大最小值。块内建凸包，二分 $kb_i+a_ib_i$。

241211

Q2064

点分治 $u$，预处理 $x$ 最早 $f_x$ 到 $u$，要走边 $(u,v,t)$ 最晚 $g_{u,t}$ 从 $u$ 出发。数满足 $f_s\le g_{ed,t},t\le lim$ 的不同颜色数量，扫描线。

241215

thupc2025 初赛 H。

对 $c$ 分解质因数，每个质数 $p$ 维护 $\frac{i}{gcd(i,a_i)}$ 是 $p$ 倍数的位置，一个个取出来修改，只有 $n\log n$ 次修改。

类似 弹飞绵羊，分块，每个点维护第一次跳出块的位置。

开更。

250207

P10061

$n\times n$ 的矩阵，$q$ 次询问。

• 将一个正方形逆时针转 $90$ 度；
• 矩阵加一个值。

$n,q\le 3000$。

神秘。

根号重构。对询问分大小为 $B$ 的块，将矩阵划分为 $4B^2$ 个子矩阵并维护原来左上角现在的坐标和旋转的次数。每次询问遍历所有的块判断在不在操作范围内并打标记，重构时再放回去。复杂度 $O(qB^2+\frac{q}{B}n^2)$。

250208

P4800

$n\times m$ 的矩形，$q$ 次询问 $(a,b,x,y)$，每个点加 $\max(a-b\times \max(|i-x|,|j-y|),0)$。最后输出矩形。

$n\times m\le 2.5\times 10^6,q\le 2\times 10^5$。

一坨屎。

每次枚举较短一边做矩阵加可以 $O(q\sqrt{nm})$，当一维顶到两边的界时对另一维加等差数列。

矩阵不断扩大时差分的位置在对角线或边界上，维护斜线和边界位置差分数组变化值的差分。

250210

P8969

区间加，区间 popcount，单点查。

做完一次 P 之后只有 $O(\log V)$ 种本质不同数值。

线段树维护区间是否有 P 操作，P 之前加了多少，对于第一次 P 后等于 $i$ 的数现在是什么。

250216

pjudge PR #15 B

树，每个节点上有一颗二叉搜索树。

• 对路径上的点的 BST 插入一个 $x$。
• 单点查询在一个 BST 上查找 $x$ 时经过的权值和。

离线。对于 $(x,t)$，贡献为比 $x$ 两侧的 $t$ 的前/后缀最小值位置上的 $y$。

线段树合并，楼房重建线段树维护前/后缀最小值位置上的和。

250218

P11369

有向图。

• 将一条边打开关闭。
• 询问 $u,v$ 是否可达。

$n\le e\times 10^4,m,q\le 10^5$。

时间分块，每 $B$ 个询问一起做，$2\times B$ 个关键点。把非关键边的拿出来缩边双，求出关键点使用非关键边两两的连通性。bitset 优化 bfs。复杂度 $O(\frac{q}{B}n\frac{B}{w}+q\frac{B^2}{w})$，乱冲。

250220

怎么两天一道了。

给定 ${a_n},k$。计数区间 $[l,r]$ 满足 $\text{mex} a_j+\min a_j+k\ge \max a_j$。

注意到 $\text{mex}$ 和 $\min$ 至少一个为 $0$。计数 $\text{mex}+k\ge \max$ 加 $\min+k\ge max$ 减去 $k\ge \max$。

$\text{mex}$ 的部分。求出 极小和极大 $\text{mex}$ 区间，即 $pl\le i\le l,r\le j\le pr$ 的区间 $[i,j]$ 的 $\text{mex}$ 值相等。再二分出 $nl$ 使得 $\text{mex}+k\ge \max_{nl\le j\le r}a_j$，和 $nr$ 使得 $\text{mex}+k\ge\max_{l\le j\le nr}a_j$。对于 $nl\le i\le l,r\le j\le nr$ 的 $[i,j]$ 符合 $\text{mex}$ 部分的限制。扫描线求矩阵并。

240221

P9598

$n$ 个点 $m$ 次加/删边操作。$q$ 次询问操作 $t$ 后 $[1,p]$ 和 $[p+1,n]$ 的导出子图的连通块数之和。

$n,m,q\le 10^5$。

在 $[1,pl]$ 的图上线段树分治，到一个时间枚举在这个时间且 $p\in [pl,pr]$ 的询问，直接加入小于当前时间且右端点属于 $[pl+1,p]$ 的边，询问，再删除这些边。

所以分块，复杂度取决于右端点属于 $[pl+1,pr]$ 的边的数量和 $[pl,pr]$ 块数。设阈值 $B$，按右端点排序大概 $B$ 条边分成一块。可以保证右端点属于 $[pl+1,pr]$ 的边数 $<2\times B$， $[pl,pr]$ 块数 $<2\times \frac{n}{B}$。

对于每一块，都要对之前的边重新线段树分治一遍；对于每个询问，都要遍历块内之前的边。所有的加边删边操作都要可撤销并查集。复杂度 $O(\frac{n}{B}n\log^2 n+mB\log n)$。取 $B=1000$ 跑的飞快。

240224

Q8229

$n$ 个栈 $q$​ 次询问。

• 对编号 $[l,r]$ 的栈 push $x$ 个 $y$。
• 对编号 $[l,r]$ 的栈 pop $x$ 次。
• 查询编号 $k$ 的栈从栈底开始 $[p,q]$ 的元素之和。

$n,q\le 10^5$。

换维，扫描线，数据结构维护时间维。

维护 $pre$ 个右括号和 $suf$ 个左括号合并。

将询问差分为两个后缀。对于一个后缀，如果全部来自右儿子，递归右儿子；否则查右侧所有左括号的权值之和，与左侧一段的权值之和，类楼房重建，合并时记录左侧被合并掉的左括号权值是多少。

将时间的一个前缀从线段树上取出，从右往左合并计算。