骷髅打金题

Undead2008 · 2024-12-11 17:00:01 · 题解

经 int_R 指正，我原来的题解有一部分在狗叫，已于 5 月 30 日修正。

暴力

因为暴力比较有意思就简单说一下。

Sub #2

固定左端点，枚举右端点，动态使用桶维护所有出现过的元素的种类数 V 和众数出现次数 T，如果 V\times T 等于区间长度 l，则该区间合法。

由此得到小常数 O(n^2) 做法。Sub #1 是给大常数做法和复杂度更高的做法留的。

Sub #3

考虑枚举出现过的元素集合 S，进行和哈希，给原序列中出现的元素随机赋权，同种元素权值相同。

如果区间所有元素的哈希值总和能被 S 中元素的哈希值总和 W_S 整除即为合法。这个可以转成前缀和模 W_S 相等，然后拿哈希表存储前缀和的哈希值就行了。

Sub #4

每一种元素的期望出现次数很少。

将每个区间 [l,r] 转成平面上的点 (l,r)，将每一种元素的贡献转成矩形取 max 然后扫描线即可。

具体可以去问验题人 cdx123456，我没写过这个做法。

正解

对原序列分治，考虑如何拼合左半边和右半边。

首先考虑和哈希，给原序列中出现的元素随机赋权，同种元素权值相同。

对“是否存在某种元素完全出现在左半边/右半边”进行分讨：

（给个图，看下面的文字感觉恶心看不懂可以看图）

如果没有任何一种元素完全出现在左半边/右半边，则每一种元素必须在左半边和右半边同时出现，此时满足条件当且仅当：

• 左边出现过的所有元素种类的哈希值和 L_a 等于右边出现过的所有元素种类的哈希值和 R_a；
• 左边和右边所有元素的哈希值总和 L_h+R_h 能被 L_a 整除，换句话说，就是 L_h\bmod L_a=(-R_h)\bmod R_a。

如果有某几种元素完全出现在左半边，没有元素完全出现在右半边，此时满足条件当且仅当：

如果要在左边加入最少的元素使得左边所有元素的出现次数相同，加入的元素哈希值总和记作 L_r。

• 有 L_r=R_h。

如果有某几种元素完全出现在右半边，没有元素完全出现在左半边，此时同上。

如果有某几种元素完全出现在左半边，有某几种元素完全出现在右半边，此时满足条件当且仅当：

左边所有出现次数严格小于众数的出现次数的元素哈希值总和记作 L_z，同理定义 R_z。

如果想要添加尽量少的元素使得左边所有元素出现次数相同，需添加的元素哈希值总和记作 L_x，同理定义 R_x。

左边所有众数在右边首次出现的位置记作 K。

• 左右两边众数出现次数相同。
• 有 L_z=R_x。

上述变量均可以线性预处理，由此得到枚举左右端点然后 check 是否满足上述四种条件其中之一的 O(n^2) 做法。

观察到上述四种情况是独立的，也就是说不可能存在区间同时满足两种或更多情况。所以可以把四种情况拆开算。

观察到上述条件大多都是检验若干个二元组或三元组完全相等，最复杂的第四种情况也只是加了一维偏序，因此可以拿哈希表直接维护，偏序可以基数排序后离线双指针，动态加动态查。

时间复杂度 O(n\log n)。哈希表需要手写。

随机赋权单个元素权值值域使用 10^9 级别冲突概率极大，使用 10^{12} 级别即可轻松通过。

代码

贺题的小先生太多了，目前已通过的提交中绝大多数都是直接复制粘贴我的题解，故于 2025/5/27 删除所有 O(n\log n) 代码。

下面是一种手写哈希表的实现：

//Hash_Table
const int MASK = (1<<19)-1;
int Hd[MASK+1],Idx;
int Ne[maxn],C[maxn];
XI Wx[maxn];
inline void Insert(const XI &X){
    const int p=X&MASK;
    for(int i=Hd[p];i!=-1;i=Ne[i])
        if(Wx[i]==X)
            return C[i]++,void();
    C[++Idx]=1,Wx[Idx]=X,Ne[Idx]=Hd[p],Hd[p]=Idx;
}
inline void Reset(const XI &X){
    Hd[X&MASK]=-1;
}
inline int Query(const XI &X){
    const int p=X&MASK;
    for(int i=Hd[p];i!=-1;i=Ne[i])
        if(Wx[i]==X)
            return C[i];
    return 0;
}