专题题解 - NOI 2023 部分题目

发表于 2025-02-24 分类于专题题解

NOI 2023

感觉不如……2021……难度……

D1T1

先假设没有斜线，只有横线和竖线，那么总点数等于每条线的点数之和减掉交点数。先加横线，然后从左到右扫描线加入竖线，求交点数就是一个单点加区间求和的线段树。

再加入斜线，我们暴力枚举每条横线和竖线看有没有与它相交，然后看看本质不同的交点有多少个就行了。

从 $n+1$ 到 $n+m$ 依次加点，维护当前前缀的虚树。每加入一个点时，有可能会额外引入一个虚树上的父亲。

设 $f(i,S)$ 表示加到了 $n+i$，$S$ 的第 $j$ 位为 $1$ 当且仅当加入 $n+i-j$ 时引入了一个还没有被认领的虚树上的父亲。

转移有两种：

$n+i+1$ 认领 $S$ 中的一个未认领的父亲，$f(i,S)\to f(i+1,S’)$，$S’$ 是 $S$ 去掉一个 $1$，左移一位末尾加 $0$ 得到的。
$n+i+1$ 加在当前树的一条边上或一个点下，$f(i,S)\times (2sz-1)\to f(i+1,S’)$，其中 $sz$ 是树的大小可以通过 $i,S$ 得出；$S’$ 是 $S$ 左移一位末尾加 $0$ 得到的。
$n+i+1$ 引入了一个父亲，$f(i,S)\times (sz-1)\to f(i+1,S’)$，$S’$ 是 $S$ 左移一位末尾加 $1$ 都得到的。

考虑 $x\to y$ 最短路，将边全部反转考虑 $y\to x$，设 $l$ 为它们的 LCA，那么可以发现一定是 $y$ 先走到 $l$ 然后沿着树边一路向下走到 $x$。

于是对于每个 $y$，我们只要算它到它的所有祖先的最短路即可，这只有 $O(\log n)$ 个点，随便乱做都可以。

$w[x:x+i-1]<w[x+i:x+2i-1]^R$，可以先统计后缀 $w[x:]$ 小于前缀反转 $w[:x+2i-1]^R$ 的方案数，等价于问一个区间里有多少个后缀排名比 $w[x:]$ 大，二维数点。

但是我们要减掉其中 $w[x:x+i-1]=w[x+i:x+2i-1]^R$ 的情况。用 manacher，枚举回文中心 $x+i-\frac{1}{2}$，可以发现以其为中心的偶回文串是否要减掉贡献是确定的，所以我们可以得出所有需要减掉贡献的情况，就看有几个能够到 $x$ 即可，又是一个数点。