自动搬运

查看原文

来自洛谷，原作者为

	wangyizhi 昨夜西风凋碧树。独上高楼，望尽天涯路。

搬运于2025-08-24 23:00:04，当前版本为作者最后更新于2025-05-08 21:31:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

神秘做法。

题目分析

记 $c_i$ 表示 $i$ 的出现次数。

首先我们先不算三个数相等的情况，最后再加上去。这样方便后面处理。

先不考虑位置顺序的限制，发现是好求的。您都开到这道题了那一定会的对吧！。记 $s$ 表示 $c$ 自己卷起来的结果，那这一部分的答案就是 $\sum c_i(s_i-c_i)$。但发现其实每个都算了两次，不过问题不大。

考虑减掉多算的部分，发现只有两种情况：$x-d,x+d,x$ 或 $x,x-d,x+d$，其中 $d \neq 0$。第二种其实和第一种是类似的，只要翻转一下重新求即可。下面考虑求第一种情况。

记现在处理到 $p$，之前每个数的出现个数为 $f_i$，那么我们有两种求法：

• 将 $f$ 自己卷起来，得到 $h$，答案为 $h_{2a_p}$。

• 枚举前面的每个数，逐个求出答案，为 $\sum f_{2a_p-a_i}$。

发现上面两种方法都是很慢的。将两种方法结合一下，类似于分块，我们可以快速将前几个块末求出的 $h$ 与这块内的散点合并。具体地，记前面几个整块末求出的个数为 $f$，自己卷积的结果为 $h$，这块内每个数的出现次数为 $g$，则答案为 $h_{2a_p}-f_{a_p}^2+\sum_{i>R} 2f_{2a_p-a_i}+g_{2a_p-a_i}$。（乘 $2$ 是因为和其它的统一一下也算两次）。

设块长为 $B$。则卷积部分复杂度为 $O(\frac{n}{B}n \log n)$，枚举计算部分为 $O(nB)$。于是 $B$ 取 $\sqrt{n\log n}$ 时最小，但由于卷积常数很大，可以再取大些。

于是就做完啦。

Code

// by wangyizhi(571247)
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
//bool Mst;
namespace wyzmath
{
	/*complex*/
	template<typename _Tp=double>
	class complex
	{
	public:
		typedef _Tp vtype;
		vtype x,y;
		complex(vtype _x=0,vtype _y=0):x(_x),y(_y){}
		vtype length(){return std::sqrt(x*x+y*y);}
	}; // class complex
	/*about complex*/
	template<typename _Tp=double>
	complex<_Tp> operator+(complex<_Tp> a,complex<_Tp> b)
	{return complex<_Tp>(a.x+b.x,a.y+b.y);}
	template<typename _Tp=double>
	complex<_Tp> operator-(complex<_Tp> a,complex<_Tp> b)
	{return complex<_Tp>(a.x-b.x,a.y-b.y);}
	template<typename _Tp=double>
	complex<_Tp> operator*(complex<_Tp> a,complex<_Tp> b)
	{return complex<_Tp>(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
	template<typename _Tp=double>
	complex<_Tp> operator+=(complex<_Tp> &a,complex<_Tp> b){return a=a+b;}
	template<typename _Tp=double>
	complex<_Tp> operator-=(complex<_Tp> &a,complex<_Tp> b){return a=a-b;}
	template<typename _Tp=double>
	complex<_Tp> operator*=(complex<_Tp> &a,complex<_Tp> b){return a=a*b;}
}
using namespace std;
using ld=long double;
using compld=wyzmath::complex<ld>;
const compld I(1,0);
const int N=1<<21,V=3e4,VV=6e4,B=5000;
const ld PI=3.141592653589793;
int rev[N];
ll a[N],c[N],s[N],d[N],e[N],p[N];
void FFT(compld *a,int n,int op)
{
	for(int i=0;i<n;i++) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
	for(int mid=1;mid<n;mid<<=1)
	{
		compld omega(cos(PI/mid),op*sin(PI/mid));
		for(int len=mid<<1,i=0;i<n;i+=len)
		{
			compld o(1,0),x,y;
			for(int j=0;j<mid;j++,o=o*omega)
				x=a[i+j],y=o*a[i+j+mid],a[i+j]=x+y,a[i+j+mid]=x-y;
		}
	}
}
void conv(ll *a,ll *b,ll *c,int n)
{
	static compld tmpa[N],tmpb[N];
	int sz=1,l=0;
	while(sz<n) sz<<=1,l++;
	for(int i=1;i<sz;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	for(int i=0;i<sz;i++) tmpa[i]=a[i],tmpb[i]=b[i];
	FFT(tmpa,sz,1),FFT(tmpb,sz,1);
	for(int i=0;i<sz;i++) tmpa[i]=tmpa[i]*tmpb[i];
	FFT(tmpa,sz,-1);
	for(int i=0;i<sz;i++) c[i]=(ll)(tmpa[i].x/sz+0.5);
	for(int i=n;i<sz;i++) c[i]=0;
}
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	int n;ll ans=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],a[i]--,c[a[i]]++;
	conv(c,c,s,VV);
	for(int i=0;i<V;i++) s[i<<1]-=c[i]*c[i];
	for(int i=0;i<V;i++) ans+=s[i<<1]*c[i];
//	cout<<ans<<"\n";
	auto sol=[&]()->void
	{
		for(int i=0;i<VV;i++) s[i]=0;
		for(int i=0;i<V;i++) d[i]=e[i]=0;
		for(int i=1,le=0;i<=n;i++)
		{
			ans-=s[a[i]*2]-d[a[i]]*d[a[i]];
			for(int j=le+1;j<=i;j++) if(a[i]!=a[j]&&a[i]*2>=a[j])
				ans-=d[a[i]*2-a[j]]*2+e[a[i]*2-a[j]];
			e[a[i]]++;
			if(i%B==0&&i!=n)
			{
				for(int j=0;j<V;j++) d[j]+=e[j],e[j]=0;
				conv(d,d,s,VV);
				le=i;
			}
		}
	};
	sol();reverse(a+1,a+n+1);sol();ans/=2;
	for(int i=0;i<V;i++) ans+=c[i]*(c[i]-1)*(c[i]-2)/6;
	cout<<ans<<"\n";
	return 0;
}