自动搬运

查看原文

来自洛谷，原作者为

	ForgotMe 花与剑无痕，高挂一轮明灯。银蝶染旧梦，生死莫再问。

搬运于2025-08-24 22:36:34，当前版本为作者最后更新于2021-11-17 20:58:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

发现这个总多样性很丑陋，我们用柿子来表示。

可以发现一种元素 $i$ 产生的贡献为

$$\dfrac{n\times (n+1)}{2}-\sum_{j=1}^{cnt_i}\dfrac{f_{i,j}(f_{i,j}+1)}{2} $$

$cnt_i$ 表示元素 $i$ 之间产生了 $cnt_i$ 个间隙，其中第 $j$ 个间隙的长度为 $f_{i,j}$，于是就用总区间的个数减去没有这个元素的区间个数。

于是可以得到总多样性

$$S=\sum_{i=1}^K(\dfrac{n\times (n+1)}{2}-\sum_{j=1}^{cnt_i}\dfrac{f_{i,j}(f_{i,j}+1)}{2}) $$

其中 $K$ 表示不同元素个数，$n$ 表示区间长度。

又注意到 $n-c_i=\sum_{i=1}^{cnt_i}f_{i,j}$，$c_i$ 为元素 $i$ 的出现次数。

于是拆拆拆，就可以得到：

$$S=\dfrac{1}{2}(KN(N+1)-N(K-1)-\sum_{i=1}^K\sum_{j=1}^{cnt_i}f_{i,j}^2) $$

于是任务为最大化 $\sum_{i=1}^K\sum_{j=1}^{cnt_i}f_{i,j}^2$。

然后就可以猜结论了。

结论 1

在一个最优解中，重排后的序列每一种数字一定都是连续的排在一起的，不会分开这里放一个那里放一个。

这个结论挺简单，证明略。

结论 2

知道了前面那个东西还是不太能做，考虑一下应该怎么摆放，显然分析到现在数字的大小并没有什么意义，而是在于每种数字的个数。

然后经过一顿猜，发现最优策略是把每种数字的个数从小到大排序，然后先第一种数字都塞头，再把第二种数字都塞尾，第三种数字都塞头，交错着塞。

感性理解一下，这样子分配会很均匀，所以不会劣。（如果要看证明的请去官方题解看那 3 页数学公式。。。）

猜到这个东西就可以 $\mathcal{O(nq\log n)}$ 了。64 pts 到手。

考虑如何维护这个东西，发现可以把每种数字的个数都塞进一个桶里，形式化的来说，设 $t_i$ 表示有 $t_i$ 种数字的个数都为 $i$。

惊奇的发现这个桶里有值的地方最多 $\mathcal{O(\sqrt{n})}$ 个，因为最坏情况为 $1+2+3+4+...+L\le n$，$L\le \sqrt{n}$。

如果我们知道桶里那些地方有值，该如何计算贡献？

假设左边已经塞了 $l$ 个数字右边塞了 $r$ 个数字，当前左边还要塞 $lput$ 种，右边还要塞 $rput$ 种，每种个数为 $len$ 的数字。

可以左边塞的这些数字造成的左边空隙的贡献之和为：

$$\sum_{i=0}^{lput-1}(i\times len+l)^2$$

这个东西很好算，拆开就是自然数 $1$ 次幂和，$2$ 次幂和。

其他的 $3$ 种情况可以仿照上面这种情况计算。

剩下的问题就是如何维护这个桶了，考虑莫队，开个 set 暴力维护桶里哪些地方有值，算贡献的时候直接把有值的地方拉出来就行了，但是这样子复杂度 $\mathcal{O}(q\sqrt{n}\log n)$，极其的不优美，而且由于洛谷的 120s 限制开不到 7s，无法通过。

考虑一下转移的时候 $\mathcal{O}(1)$ 转移，可以开一个操作栈记录下所有的转移（插入一个数字/删除一个数字），把数字拉出来的时候就看最后一次操作到底是插入还是删除（显然只有最后一次操作才有影响），但是拉出来的数字可能无序，需要排序，注意到拉出来的数字最多会有 $\mathcal{O}(\sqrt{n})$ 个，于是复杂度就只有 $\mathcal{O}(q\sqrt{n}+q\sqrt{n\log n})$，可以通过此题，如果你想 $\mathcal{O}(q\sqrt{n})$，请使用基数排序。。。

丑陋的代码

#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL long long
inline int rd(){
	char c;
	int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-'0';
	return x*f;
}
#define mp make_pair
#define pp pair<int,int> 
int n,q,B,bl[300005],tong[300005],col[300005],len,c[2][300005],a[300005],K,oplen,num[1200005],Num[300005];
bool ok[300005];
pp opr[1200005];
LL ans[50005];
struct que{
	int l,r,id;
}Q[50005];
bool cmp(que a,que b) {
	return (bl[a.l]^bl[b.l])?bl[a.l]<bl[b.l]:((bl[a.l]&1)?a.r<b.r:a.r>b.r);
}
set<int>S;
set<int>::iterator it;
void add(int x){
	tong[col[a[x]]]--;
	if(!tong[col[a[x]]])opr[++oplen]=mp(-1,col[a[x]]);
	col[a[x]]++;
	if(col[a[x]]==1)K++;
	tong[col[a[x]]]++;
	if(tong[col[a[x]]]==1)opr[++oplen]=mp(1,col[a[x]]);
}
void dec(int x){
	tong[col[a[x]]]--;
	if(!tong[col[a[x]]])opr[++oplen]=mp(-1,col[a[x]]);
	col[a[x]]--;
	if(col[a[x]]==0)K--;
	tong[col[a[x]]]++;
	if(tong[col[a[x]]]==1)opr[++oplen]=mp(1,col[a[x]]);
}
LL Sum1(int n){
	return 1ll*n*(n+1)/2;
}
LL Sum2(int n){
	return 1ll*n*(n+1)*(2*n+1)/6;
}
//0 1 2
LL calc1(int N,int c,int len){
	return 1ll*c*c*(N+1)+1ll*Sum2(N)*len*len+2ll*Sum1(N)*len*c;
}
LL calc2(int N,int c,int len){
	return 1ll*c*c*(N+1)+1ll*Sum2(N)*len*len-2ll*Sum1(N)*len*c;
}
//i^2len^2+2*i*lenl
LL solve(int L,int R){
	int nlen=0;
	for(int i=oplen;i>=1;i--){
		if(ok[opr[i].second])continue;
		ok[opr[i].second]=1;
		if(opr[i].first==1)Num[++nlen]=opr[i].second;
	}
	for(int i=1;i<=len;i++){
		if(ok[num[i]])continue;
		ok[num[i]]=1;
		Num[++nlen]=num[i];
	}
	for(int i=oplen;i>=1;i--)ok[opr[i].second]=0;
	for(int i=1;i<=len;i++)ok[num[i]]=0;
	len=nlen;
	for(int i=1;i<=len;i++)num[i]=Num[i];
	sort(num+1,num+len+1);
	for(int i=1;i<=len;i++){
		c[0][i]=num[i];
		c[1][i]=tong[num[i]];
	}
	//表示长度为 (*it) 的有这么多个 
	int l=0,r=0,tot=0,N=R-L+1;
	LL Ans=0;
	for(int i=1;i<=len;i++){
		int lput=0,rput=0,Len=c[0][i];
		if(tot%2==0){
			lput=(c[1][i]+1)/2;
			rput=c[1][i]/2; 
		}else{
			rput=(c[1][i]+1)/2;
			lput=c[1][i]/2; 
		}
		Ans+=calc1(lput-1,l,Len);
		Ans+=calc2(lput-1,N-l-Len,Len);
		Ans+=calc1(rput-1,r,Len);
		Ans+=calc2(rput-1,N-r-Len,Len);
		l+=lput*Len,r+=rput*Len; 
		tot+=c[1][i];
	} 
	return 1ll*(1ll*K*N*(N+1)-1ll*N*(K-1)-Ans)/2;
}
int main() {
	scanf("%d %d",&n,&q);
	B=sqrt(n*1.0);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)bl[i]=(i-1)/B+1;
	for(int i=1;i<=q;i++)scanf("%d %d",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q+1,Q+q+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=q;i++){
		int L=Q[i].l,R=Q[i].r;
		oplen=0;
		while(l<L)dec(l),l++;
		while(L<l)l--,add(l);
		while(r<R)r++,add(r);
		while(R<r)dec(r),r--;
		ans[Q[i].id]=solve(L,R);
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
    return 0;
}