duel 记录
省流，juju 太菜了，总共 win 了 2 把。
数据实时更新。
1. ？
?
hzr 胜 juju。
是一个低分题，皇子很快秒了，我根本没读懂题意。
2. Jzzhu and Squares
*2900
juju 胜 hzr。
这个题我和皇子都做了非常久。
题意是求格点正方形完整包含的格子个数，注意到格点正方形可以是由“三垂直”结构构成的斜的正方形。
我们考虑一个横平竖直的 \(n\times n\) 的正方形的贡献 \(f(n)\)。
\(f(n)=n^2+\sum_{i=1}^{n-1}(n-2i)^2+4g(i,n-i)\)。
\(g(i,j)\) 是两条直角边为 \(i,j\) 的等腰三角形内的完整格点数。运用皮克定理可以得到 \(g\) 的式子。
完整的式子推导比较繁琐，最终的式子仅需要知道 \(\text{id}\times\varphi(i)\)，可以写狄利克雷卷积也可以线性筛。
时间复杂度 \(O(n\ln n)\) 或 \(O(n)\)。
3. Karen and Cards
*2800
hzr 胜 juju。
自己编的做法很多细节，而如果基于值域 \(5\times 10^5\) 的话可以使用线段树做法将细节减少非常多。
说说我自己的做法。
考虑按 \(a,b,c\) 分别降序排序之后，一个三元组 \((x,y,z)\) 显然会输给三个维度的三个前缀。
而有贡献的三元组等价于对应的三个前缀没有重复元素。
我们考虑枚举 \(a\) 维的前缀 \(i\)，此时 \(b\) 维和 \(c\) 维分别有一个红线不能越过。而 \(b,c\) 在此时一定是一个单调不降和单调不升的双指针结构的贡献。
我们可以提前预处理出 \(b\) 往后扫，\(c\) 往前扫的贡献，\(a\) 维的限制很好处理，我们截取一段 \(b\) 的区间即可，可以用二分实现。
时间复杂度 \(O(n\log n)\)。
4. Yet Another LCP Problem
*2600
zph 胜 juju。
写了一个 \(O(n\log^2n)\) 的 SAM 上树剖做法，调试太慢了败给了 zph/ll。
做法是经典的 [LNOI] LCA。
5. Even Harder
*2700
hzr 胜 juju。
啊啊啊，DP 题被皇子薄纱。这个题思路来得很快但是写起来被莫名其妙的细节卡了好久。
一个朴素的 DP 可以考虑 \(f(i,j)\) 表示处理完 \([i,n]\)，从 \(i\) 出发到 \(n\) 只有一条路径，这条路径上的后面一个点是 \(j\)，最少赋 0 次数。转移考虑枚举下一个路径上的位置即可，容易 \(O(n^3)\)。
优化可以试图将状态里的 \(j\) 这一维去除，考虑如果我们能直接不转移到能一步到达 \(j\) 的位置就好了。
我们可以将元素按 \(i+a_i\) 降序排序 DP，\(f(i,j)\) 表示处理到排名为 \(i\) 的元素，那一条唯一能到 \(n\) 的路径的最后一个点是 \(j\) 时的最少赋 0 次数。
如果我们需要将此时的节点加入路径，我们将第一维跳到 \(i+a_i<j\) 的第一个位置，越过所有不合法的位置，将区间里需要赋 0 的元素统计进代价。
时间复杂度 \(O(n^2)\)。
6. Appropriate Team
*2700
xzy 胜 juju。
这题做了好一会儿不会，xzy 都过了，终于去想对不同质因子分开考虑，很快会做了。
我们对于质因子 \(p\) 考虑题目给定限制：
\(\exist v,\min(v_p(v),v_p(a_i))=v_p(X),\max(v_p(v),v_p(a_j))=v_p(Y)\)。
条件不满足当且仅当 \(v_p(a_i)\neq v_p(X)\and v_p(a_j)\neq v_p(Y)\and v_p(X)\neq v_p(Y)\)。
我们把 \(\dfrac Y X\) 的质因子拿出来，只有这些质因子满足 \(v_p(X)\neq v_p(Y)\)，由于 \(\omega(10^{18})=15\)，我们对这些质因子做 FWT 是很轻松的。
时间复杂度 \(O(V^{1/4}+2^{\omega(V)}\omega(V))\)。
7. Minimum Difference
*3100
juju 胜 hzr。
时限 5s，数据范围全是 1e5，试试带修莫队。
考虑莫队时维护出每个数的 occ 和 occ 为 \(i\) 的数的个数。
我们所求即为在后者数组上，最小的一个区间使得区间和不少于 \(k\)。
而有值的位置不超过 \(\sqrt n\) 个，我们可以维护有值的位置拿下来双指针。
我实现的做法是 \(O(\dfrac{n^2}{w}+带修莫队+m\sqrt n)\)。
带修莫队的块长乱设的，感觉 5s 随便过。
8. Number of Components
*2800
zyf 胜 juju。
为啥题面是 \(c_i\le\max(1000,2\times 10^6/n/m)\) 啊/fn/fn。
首先一个一眼的做法是线段树分治，\(O(q\log q\log(nm))\)，空间 \(O(q\log q)\)，感觉过不去。
我们考虑利用好题目里的特殊性质 \(c_i\le c_{i+1}\)。
观察到直接做并查集难以维护的原因是会有分裂操作。
我们可以倒过来做将分裂转化成合并操作，具体的可以维护 \(<c\) 的并查集，到 \(p\) 的修改时将 \(p\) 的点全部删掉，这个部分的贡献正着扫的时候求得。
时间复杂度 \(O(q\log (nm)+Cnm)\)。