【题单】wzy

QOJ5402 术树数

将所有的环插入线性基，包括边走两次形成的环。
然后线性基主元就是做 gcd。复杂度 \(O((n+q)\log^2 k)\)。

P15939 [JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater

假设前面和为 \(s\)，扫到一个段符号是 \(c\)，长度为 \(x\)：

• \(c=\) -：\(s'=\max(0,s-x)\)。
• \(c=\) +：\(s'=(s+x)\bmod k,ans'=ans+\left\lfloor \frac{s+x}{k} \right\rfloor\)。

如果没有 \(\max\) 答案就是求和除以 \(k\)。
考虑 \(nxt_i\) 表示从第 \(i\) 段开始，往后到第几段 \(s\) 会变成 0。
即 \((pre_{nxt_{i}-1}-pre_{i-1})\bmod k\le -a_{nxt_i}\)，倒着扫描线并维护线段树最值即可。
查询就是倍增。第一段和最后一段特殊处理。

P15940 [JOI Final 2026] 花园 3 / Garden 3

找到 \(v\ge X\) 的最左侧格子，其他方向同理。
找到每个 x 作为答案的时间区间，维护当前时间 \(t\)，x 增加会导致 \(t\) 减小。

P15944 [JOI Final 2026] 传送机 2 / Teleporter 2

\(f_{i,k}=\min_{j>i} f_{j,k-1}+\sum_{[i\le S<T<j]} C\)，代价满足四边形不等式，wqs 二分，里面扫描线。

2026 广东省集 R1D1T2 谜题

题面描述
汤圆和元宵在玩一个数字游戏：给定一个正整数 \(n\)，汤圆会选择一个 \(1\sim n\) 的正整数 \(c\)，每次元宵可以选择一个正整数集合 \(S\) 并询问汤圆是否在 \(S\) 中，汤圆在所有回答中至多说谎一次。
现在已知元宵的第一次询问的 \(S\) 是 \(1\sim u\) 组成的集合，\(n=u+v\)，并且汤圆回答“是”，我们记此时元宵最少要额外问 \(f(u,v)\) 次来确定 \(c\) 的值。特别的，我们认为\(f(0,0)=0\)。
给出 \(q\) 组询问，每次给定 \(l_0,r_0,l_1,r_1\)，请求出 \(l_0\le u\le r_0,l_1\le v\le r_1\) 的所有 \(f(u,v)\) 之和对 \(2^{64}\) 取模的结果。

---

设状态 \((a,b)\) 表示 \(a\) 个数没有被否认，\(b\) 个数被否认过一次。
设 \(g_{a,b}\) 表示该状态下的最小步数，则有 \(g_{a,b}=\min_{x,y}\max(g_{x,a-x+y},g_{a-x,x+b-y})\)。
结论：\(S_i=\{(a,b)\mid g_{a,b}\le i\}=\{(a,b)\mid a\le lim_i,b\le 2^i-(i+1)a\}\)。其中 \(lim_i\) 是一个需要求的东西。
\(\color{Red}\mathtt{\Gamma}\)

P9334 [JOIST 2023] 水羊羹 2 / Mizuyokan 2

峰满足 \(\max(a_{l-1},a_{r+1})<sum\)，谷其实不需要考虑限制，可以变成长度为 1 的，满足峰一定合法。
这样只要划分峰，且不要求紧挨着。
对于每个 \(i\) 求出 \([i,nxt_i]\) 中存在一个合法的峰段，\(nxt_i-i=O(\log_{\varphi} V)\)。
弹飞绵羊。

CTT 2025 Day 1 异形工厂

移动代价：\(\left\lceil \frac{dis}{2}\right\rceil\)。
先考虑没有上取整，计算 \(pre_i=\sum_{j\le i}(s_j-t_j)\)，可以划分为若干段 \(pre_i=pre_{l-1}\) 的，其中 \(pre_r=pre_{l-1}\) 否则无解。那么给这 \(O(n)\) 个段都求出答案，然后对同高度做前缀和。
段内分为向左匹配或者向右匹配，按照这个分为两个集合，一个集合内的所有段要么包含要么不交，所以可以建出一棵树。
那么一个区间的答案就是其儿子的匹配，然后加上 \(l,r\) 的匹配。

---

回到原问题，暴力 \(O(nq)\) 就是维护奇偶位置的左括号，然后遇到右括号就是优先匹配同奇偶的，否则答案额外加一。
考虑用上述的树形结构优化，考虑加入 \(l,r\) 如何调整。如果 \(l\) 是奇数，那么找到一个 偶-奇 的匹配，然后把 偶 拆出来找下一个 奇-偶 的匹配...
奇-偶 和 偶-奇 的匹配连成一个链表，每次相当于同种匹配的连续段长度减一。
总复杂度 \(O(n)\)。

LOJ5658 「POI2026 R3」Dyscyplina

\(n\le \log V\)，否则一定最后是搬 \(a_n\)。
Hall 定理判定一段前缀时间 \(mid\) 是否可以匹配：\(\forall S,\sum_{t=1}^{mid} [t\mathrm{\ and\ }S>0]-\sum_{i\in S} a_i\ge 0\)。
数位 dp 处理这个东西 min。