自动搬运

查看原文

来自洛谷，原作者为

	Undead2008 。

搬运于2025-08-24 23:16:48，当前版本为作者最后更新于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$。
• $K$ 大于右边的右端点 $r$。换句话说，就是左边的所有众数均不在右边出现。

上述变量均可以线性预处理，由此得到枚举左右端点然后 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;
}

$O(n^2)$ 的代码如下：

#include"bits/stdc++.h"
using namespace std;
const int maxn = 1e6+10;
int T,n,m;
int Ap[maxn],a[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(nullptr);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		long long Ans=0;
		for(int l=1;l<=n;l++){
			for(int r=l,Mx_=0,Cc_=0;r<=n;r++){
				if(!(Ap[a[r]]++))Cc_++;
				Mx_=max(Mx_,Ap[a[r]]);
				if(Mx_*Cc_==(r-l+1))Ans++;
			}
			for(int r=l;r<=n;r++)Ap[a[r]]=0;
		}
		cout<<Ans<<'\n';
	}
}