THUWC&WC 游记

· · 生活·游记

WC 场内选手爆零寄

赛时一道题都没看懂（

T1 代码堵塞

绿题都切不了真是失败啊

可能是受前一天晚上神 WZX 说准备拿两位数的影响（雾

T2 水镜

计数的问题先学会怎么判断

​ ——cmd

先考虑 L 确定时怎么做。

记 p_i 表示 \max\{h_i,2L-h_i\}，然后小的就是 2L-p_i。

不难想到贪心地前面取小的，后面取大的，因此合法的充要条件显然就是存在一个分界线 w\in[u,v)，使得 2L-p_i 在 [u,w] 递增和 p_i 在 (w,v] 递增而且 2L-p_w<p_{w+1}。

转化一下就是 p_i 在 [u,w] 递减，在 (w,v] 递增，且 p_w+p_{w+1}>2L。

注意到 p_w+p_{w+1}=\max\{h_w,2L-h_i\}+\max\{h_{w+1},2L-h_{w+1}\}\ge 2L，因此只要关心 h_w 和 h_{w+1} 不都等于 L 就可以了。

如果 L 变化呢？

注意到我们只关心 p_i 和 p_{i+1} 的相对大小关系。

不妨令 h_i<h_{i+1}，一顿分讨之后我们发现

p_i<p_{i+1}\iff L<\frac{h_i+h_{i+1}}2\\ p_i=p_{i+1}\iff L=\frac{h_i+h_{i+1}}2\\ p_i>p_{i+1}\iff L>\frac{h_i+h_{i+1}}2

另一种情况就是反过来

如果 h_i=h_{i+1}，p_i 必然等于 p_{i+1}，此时唯有让 w=i 方有一线生机，即 L\ne i

于是对于一对 (u,v) 只要把所有的约束取个交集，如果非空就是合法的。

可是这个方法还要枚举 w，真是太不牛了。

注意到 \exist w,p_u>p_{u+1}>\cdots>p_{w}?p_{w+1}<p_{w+2}<\cdots<p_v 当且仅当不存在 i\in(u,v),p_{i-1}\le p_i\ge p_{i+1}。

这个相当于每次扣掉一个区间，直觉告诉你其实这些区间并起来的连续区间数量不会很多，然后暴力搞就可以了。

还得让 \forall i\in[u,v)且 h_i=h_{i+1},L\ne h_i。相当于加上一些端点，但是因为上面扣掉的区间都是闭区间，所以我们可以不用管这些点。

因为这个东西应该不支持删除，所以用不删尺取（省流：用两个栈 cosplay 队列 cosplay 双指针，长得莫名像日本語www）维护极长的 (u,v) 就可以了。

T3 线段树

参考了 @A_zjzj 提供的做法

首先对于 S 中的区间 [L,R) 把 L 向 R 连一条边。

然后区间 [L_i,R_i) 是可以表示的当且仅当 L_i 和 R_i 是连通的。

我们要求的就是统计使得这 M 个点对连通的生成子图的数量。

考虑把这个图画出来。然后你发现这个图的对偶图刚好就是原来的「线段树」：根节点表示 [0,n) 的区间而每个叶子节点是一个长度为 1 的区间，按照线段树的形式组织在一起。

在原图中选择一条边相当于在对偶图中割掉一条边，于是 L_i 和 R_i 在原图中连通当且仅当对偶图中 [L_i,R_i) 的所有叶子节点都不与外部（根节点和外面的叶子节点）相连。

然后你发现可以根据 [L_i,R_i) 将 [0,n) 划分为若干不交的区间（如果有交可以分裂），使得每个区间内的叶子都不与外界往来，可以使用异或哈希的方式将其划分。

也可以理解为当且仅当 [u,u+1) 和 [v,v+1) 上覆盖的 [L_i,R_i) 区间的集合一样时才能够连接，于是划分为若干等价类。

然后就可以树形 DP 了。

可以给每个等价类标定一个颜色，因为要求不同等价类不能相连，于是每个枝干节点也只有一个颜色，而且不同颜色之间的边必须割掉。当然枝干节点也可以没有颜色，此时它不与任何叶子节点相连。

然后设 f_{u,c} 表示 u 的颜色是 c 的方案数，g_u 表示 u 没有颜色。然后有

f_{u,c}=f_{ls,c}\times f_{rs,c}+f_{ls,c}\times(2\cdot g_{rs}+\sum_{c'}f_{rs,c'})+(2\cdot g_{ls}+\sum_{c'}f_{ls,c'})\times f_{rs,c}\\ g_u=(2\cdot g_{ls}+\sum_c f_{ls,c})\times(2\cdot g_{rs}+\sum_c f_{rs,c})

当然，可以令 g_u\gets 2\cdot g_u+\sum_c f_{u,c}，然后就有

f_{u,c}=f_{ls,c}\times f_{rs,c}+f_{ls,c}\times g_{rs}+g_{ls}\times f_{rs,c}\\ g_u=2\cdot g_{ls}\times g_{rs}+\sum_c f_{u,c}

用线段树合并维护 f 就可以了题目标题都提示了算法了

对于根节点，它连往外面的边可以不选，如果选了的话，其颜色一定不能包括任何区间，因为你不能让 [L_i,R_i) 的叶子由根节点跑出去。

第一次做这种还带个乘法操作的线段树合并

note: 用std::mt19937会哈希冲突，可以用std::mt19937_64以避免