CCPC Wannafly Camp Day5
C. Self-Adjusting Segment Tree
题意
给定线段树的 $m$ 次区间查询操作，要求构造一棵维护区间 $[1,n]$ 的特殊线段树。
使得查询操作访问结点的次数最少的结点并输出访问结点的次数。
题解
不难得到 $\text{dp}$ 方程
$$ \text{dp}(i,j)=\min(\text{dp}(i,k)+\text{dp}(k+1,j)+w(i,j)) $$
然后考虑依次处理每个询问 $[ql,qr]$ 对 $w(i,j)$ 的贡献。不难发现当 $[i,j]$ 与 $[ql,qr]$ 相交但 $[i,j]\not\subseteq [ql,qr]$ 时询问贡献为 $1$。
问题在于 $[i,j]\subseteq [ql,qr]$ 询问对 $w(i,j)$ 的贡献与询问是否包含 $[i,j]$ 区间的祖结点有关。
有结论任意二叉树的叶子结点数 $=$ 非叶子结点数 $+1$，而线段树恰好为二叉树。
于是不妨转化思路令 $[i,i]\subseteq [ql,qr]$ 得到贡献 $1$，令 $[i,j](i\lt j)\subseteq [ql,qr]$ 得到贡献 $-1$。
于是 $\text{dp}$ 过程中如果划分区间得到 $[i,j]\subseteq [ql,qr]$，则 $[i,j]$ 的子树的总贡献恰好为 $1$。
对应每个询问对 $w(i,j)$ 的贡献，差分维护即可，时间复杂度 $O(n^3+m)$。
J. Xor on Figures
题意
给定 $2^k\times 2^k$ 的一个二维 $01$ 串。定义 $B(x,y)$ 表示将二维 $01$ 串循环左移 $x$ 格循环上移 $y$ 格的新二维 $01$ 串。
定义两个二维串之间的异或为对应位置异或。问任意个 $B(x_i,y_i)$ 异或能得到的所有不同的二维 $01$ 串个数。
题解
直接把 $B(x,y)$ 拉成一维，然后高斯消元计算所有 $2^{2k}$ 个 $B(x,y)$ 的秩即可。时间复杂度 $I\left(2^{4k}+\frac {2^{6k}}w\right)$。
