NOIP2024 记录

edit

贪心 in 1h，感觉挺对。

一个极大的连续

1

段中的所有位置可以任意交换，

0

的位置只能固定。依据题面可以直接将

s_1,s_2

划分成若干段，每段内可以随意排列，记录每段的

l,r,c_0,c_1

分别表示左右端点、

0/1

的数目。

直接贪，如果前面位置能够匹配就一定直接匹配完，这样不会有本能匹配的最后匹配不了。维护两个指针

i,j

代表匹配到

s_1

的第

i

段和

s_2

的第

j

段。记

x=\min(c_0(i)+c_0(j)),y=\min(c_1(i),c_1(j))

，这两段之间的匹配对答案的贡献是

x+y

：

$r_i=r_j$ ， $r_i$ 之前的地方全部做完， $i\to i+1,j\to j+1$ 。
$r_i<r_j$ ，这次处理的长度 $len=r_i-\max(l_i,l_j)+1$ 。考虑如果贡献小于 $len$ ，有一些位置不能匹配。若 $x<c_0(i)$ ，则这部分有一些在 $i$ 中为 $0$ 的位置只能用 $j$ 中的 $1$ 填，故令 $c_1(j)\to c_1(j)-c_0(i)+x$ ；否则 $i$ 中的一些 $1$ 只能用 $j$ 中的 $0$ 填， $c_0(j)\to c_0(j)-c_1(i)+y$ 。最后 $i\to i+1$ 。
$r_i>r_j$ 同理。

时间复杂度

O(Tn)

。

assign

签到题，小于 T1，1h。

特判掉

c_i=c_j,d_i\neq d_j,ans=0

和

v=1,ans=1

。

乘法原理，讨论每个位置

i

的贡献系数，全部乘起来就是答案：

$i,i+1$ 都被钦定： $a_i=x_i$ 时 $b_i=x_{i+1}$ ，否则 $b_i$ 任意，贡献系数为 $v(v-1)+1$ 。
$i$ 被钦定， $i+1$ 未钦定：所有 $(a_i,b_i)$ 的选取方法都合法， $v^2$ 。
$i$ 未钦定， $i+1$ 已钦定：所有 $(a_i,b_i)$ 的选取方法都合法， $v^2$ 。
$i,i+1$ 都未钦定， $v^2$ 。

可以将连续的全被钦定/全未钦定的合成一段，快速幂算出整段的贡献。唯一的问题是对于

10\cdots01

的区间

[i,j]

，如果

a_i=x_i

并且一路钦定下来，

b_{j-1}

必须等于

x_j

而不能任选。所以这个区间的方案数是

(v^2)^{j-i}-v^{j-i}+v^{j-i-1}

。

O(Tm\log n)

。

traverse

还不会。

query

一个扫描线 + 线段树能做的东西以为要树套树，没有冲出链的性质，遗憾离场。

无关正解的暴力：只有长度等于

k

的区间有用。一个结论是一个点集所有点的 LCA 是其中 dfn 最小的和 dfn 最大的两个点的 LCA。枚举

len-k+1

个区间和答案取

\max

，可以 dfs 序/欧拉序

O(1)

LCA 做到

O(n\log n+nq)

。

考虑正解。上面的瓶颈在于枚举区间，没有前途。考虑一个点

u

能否作为 LCA 贡献

dep_u

到询问区间。考虑预处理出所有 LCA 为

u

的极长区间。进行一个 dsu on tree，把所有儿子的区间集合合并到

u

，启发式合并 set，如果有两段区间相邻就合成一个，合成区间时顺便把这些有贡献的区间记录下来（没有和其它区间合并的区间 LCA 肯定在某个儿子的子树里，不需要重复记）。这样有贡献的区间就只有

n

个单点和

n-1

个其它的区间。这部分

O(n\log^2 n)

。

接下来就是有一些贡献区间

(l,r,w)

和询问区间

(L,R,k)

。

(l,r,w)

对

[L,R,k]

有贡献当且仅当

|[L,R]\cap[l,r]|\ge k

。分类讨论：

$l_i\le L,r_i\ge L+k-1$
$r_i\ge R,l_i\le R-k+1$
$r_i-l_i+1\ge k,l_i\in[L,R-k+1]$

前两个直接二维数点，树状数组维护前/后缀 max；最后一个将贡献区间和询问区间按照

r_i-l_i+1

或

k

从大到小排序，贡献区间的

w_i

挂在

l_i

，询问区间 max 容易线段树解决。这部分

O((n+m)\log n)

。

总时间复杂度

O(n\log^2 n)

，可以通过。其实 dsu on tree 部分合并区间还能通过并查集维护做到单 log，

O(n\log n)

。

文章操作