做题记录 25.10.22

· · 个人记录

QOJ #10272. Majority Graph

令 x(l,r) 为区间 [l,r] 的绝对众数，定义存在绝对众数的区间合法

对于合法区间 [l,r]，若 a_l\ne x(l,r) 且 a_r\ne x(l,r)，令 s,t 分别为 [l,r] 中 x(l,r) 第一次和最后一次出现，则 [l,t]，[s,r]，[s,t] 必然也合法，因此 l-t-s-r 连通，无需考虑区间 [l,r]

因此只需要考虑 a_l=a_r=x(l,r)，a_l=x(l,r)\ne a_r，a_l\ne x(l,r)=a_r 的情况，显然后两种相同，只考虑前两种

对于第一种情况，枚举 x(l,r)=v，取出 v 所有出现位置 p_{1\sim k}，令 c_x 为 a_{1\sim x} 中 v 出现次数减去其它数字出现次数，需要连接所有满足 (c_{p_i-1}<c_{p_j})\iff (c_{p_i}\le c_{p_j}) 的 p_i,p_j，实际上只需要对于每个 c_{p_i} 连接下一个 c_{p_j}\mid p_j=p_i\lor p_j=p_i+1 即可，其它的边都是多余的，容易 O(k) 完成连边

对于第二种情况，枚举 x(l,r)=v，枚举 [l,r) 中最后一个 x(l,r) 位置为 p_i，显然 l 取 v_{p_j} 最小且 j<i 的 p_j 最优，此时需要把区间 [p_i,\min(n,p_i+(v_{p_i}-v_{p_j}))] 都并起来，容易做到 O(k) 次

问题转化为 O(\sum k)=O(n) 次两点合并与区间合并，后者可以令 t_x 表示 x 是否和 x+1 合并然后维护 t 的差分做到 O(n)

总时间复杂度 O(\sum n)

代码

参考