水题乱做

P11746

设 $R$ 为单色行的数量，$C$ 为单色列的数量。
根据题意，AI 的得分 $S_{AI} = R + C$，你的得分 $S_P = (n - R) + (m - C) = n + m - (R + C) = n + m - S_{AI}$。

获胜条件是 $S_P$ 为奇数且 $S_{AI}$ 为偶数。
代入 $S_P$ 的表达式：$n + m - S_{AI}$ 为奇数。
由于 $S_{AI}$ 必须为偶数，那么 $n + m - \text{偶数} = \text{奇数}$，这意味着 $n + m$ 必须是奇数。

结论 1：如果 $n + m$ 是偶数，不可能同时满足条件，方案数为 0。
结论 2：如果 $n + m$ 是奇数，我们只需要计算 $S_{AI} = R + C$ 为偶数的方案数（此时 $S_P$ 必然为奇数）。

我们需要计算 $R + C$ 为偶数的方案数。设 $N = 2^{nm}$ 为总方案数。
令 $Ans$ 为所求方案数。

我们可以通过计算统计量 $S = \sum (-1)^R (-1)^C$ 来辅助求解。
如果我们将所有棋盘分为两类：$R+C$ 为偶数的集合 $E$（大小为 $Ans$），$R+C$ 为奇数的集合 $O$。
则：

1. $E + O = 2^{nm}$
2. $E - O = S$
   两式相加得 $2E = 2^{nm} + S \implies Ans = \frac{2^{nm} + S}{2}$。

然后分类讨论，我们可以推导出：

$$ S = (2^m - 4)^n + (2^n - 4)^m - 2^{nm} + 2 \cdot \Delta_B $$
其中 $\Delta_B$ 是与“黑色单色线”相关的加权和：
$$ \Delta_B = Z - (2^m - 2)^n - (2^n - 2)^m + 2^{nm} $$
而 $Z$ 是一个可以通过 $O(n)$ 计算的求和项：
$$ Z = \sum_{s=0}^n \binom{n}{s} (-2)^s (2^{n-s} - 2)^m $$

综合整理，$Ans = \frac{1}{2} \left[ 2^{nm} + (2^m-4)n + (2^n-4)m + 2Z - 2(2^m-2)n - 2(2^n-2)m + 2^{nm} \right]$
化简后：
$$ Ans = 2^{nm} + Z + \frac{1}{2} \left[ (2^m-4)n + (2^n-4)m - 2(2^m-2)n - 2(2^n-2)m \right] $$

期望得分 $100$ 分，实际得分 $100$ 分。

qoj9492

我们需要维护两个树上的数据。操作涉及在 $T_1$ 上进行路径加值，在 $T_2$ 上进行路径求和。
显然，问题可以转化为：

1. 每个节点 $u$ 可以映射为一个二维点 $(dfn1[u], dfn2[u])$。
2. $T_1$ 上的路径修改对应于 $dfn1$ 维度上的若干区间加值。
3. $T_2$ 上的路径查询对应于 $dfn2$ 维度上的若干区间求和。

问题本质上就是二维区域权值维护。由于操作是在线的，且 $N, M$ 较大，直接使用二维线段树或树套树空间和时间开销较大。

我们可以对 $X$ 轴（即 $dfn1$）进行分块。

• 将 $X$ 轴分成 $\sqrt{N}$ 个块。
• 每个块内部存储该块内的点，并按 $Y$ 轴（$dfn2$）排序。
• 每个块维护一个懒标记 $tag$（用于整块加值）和块内点权的前缀和数组（用于快速查询）。

对于每次修改，在 $T_1$ 上通过 HLD 分解为 $O(\log N)$ 个 $X$ 区间。对于每个区间：

• 若区间完全覆盖某块，更新该块 $tag$。

• 若区间部分覆盖某块，暴力更新块内节点的权值 $A$，并重构该块的排序前缀和数组。

对于每次查询，在 $T_2$ 上通过 HLD 分解为 $O(\log N)$ 个 $Y$ 区间。对于每个区间：

遍历所有块。在块内二分到 $Y$ 区间对应的点集，结合前缀和与 tag 计算贡献。

设块大小为 $B$。

• 修改：整块 $O(N/B)$，零散部分 $O(B)$。HLD 乘 $\log N$。总复杂度 $O(M \log N (N/B + B))$。
• 查询：遍历块 $O(N/B)$，二分 $O(\log B)$。HLD 乘 $\log N$。总复杂度 $O(M \log N \cdot \frac{N}{B} \log B)$。
  取 $B \approx \sqrt{N \log N}$ 可达到平衡。

期望得分 $100$ 分，实际得分 $36$ 分，可能需要卡常。

考虑去掉二分。

我们可以维护一个 $cnt_{y,b}$，表示在块 $b$ 中，$dfn2$ 值小于等于 $y$ 的节点数量。由于块内节点是按 $dfn2$ 排序的，$cnt_{y,b}$ 的值恰好就是二分到的下标。查询复杂度降为 $O(\frac{N}{B} \log N)$。

最优块大小应为 $\sqrt{N} \approx 450$。

期望得分 $100$ 分，实际得分 $100$ 分。