容斥原理

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=2e5+10;
inline int C(int n){
	if(n<2)return 0;
	return  n*(n-1)/2;
}
map<pair<int,int>,int> mp1,mp2,mp3;
map<tuple<int,int,int>,int> mp;
int n,ans,a[N]; 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		ans=0;
		mp.clear();
		mp1.clear();
		mp2.clear();
		mp3.clear();
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n-2;i++){
			mp[make_tuple(a[i],a[i+1],a[i+2])]++;
			ans+=mp1[{a[i],a[i+1]}]++;
			ans+=mp2[{a[i+1],a[i+2]}]++;
			ans+=mp3[{a[i],a[i+2]}]++;
		}
		for(auto p:mp)
			ans-=C(p.second)*3;//去除重复计算的贡献
		cout<<ans<<"\n";
	}
}

题解并不想用$map<pair<int,int>,int>$和$map<tuple<int,int,int>,int>$，但这样存入过程中的$M=1e7$就比较费解了，我就讲一下最为普通，最好理解的做法

题意

给定一个长度为 n 的数列 a。考虑 n−2 个关于 a 的三元对 $[a_i,a_{i+1},a_{i+2}]$。我们定义两个三元对是美丽的，当且仅当他们只有一个位置不同。

求这 n−2 个三元对中，美丽的三元对数量。

考虑

这道题枚举是肯定不可行的，$t<=1e4,N<=2e5$，枚举$O(t((n-3)*(n-4)/2))$是肯定$TLE$的，所以最好的就是$O(tn)$，那什么能达到呢？？？

其实就是容斥，看完题目应该也能比较好想到：

如图，黄色1号是$a_i=b_i,a_{i+1}=b_{i+1}$的美丽三元组

黄色2号是$a_i=b_i,a_{i+2}=b_{i+2}$的美丽三元组

黄色3号是$a_{i+1}=b_{i+1},a_{i+2}=b_{i+2}$的美丽三元组

蓝色就是$a_i=b_i,a_{i+1}=b_{i+1},a_{i+2}=b_{i+2}$的美丽三元组，但它可以被包含到$1,2,3$三种情况里面，所以答案如图所示

所以，我们可以考虑使用 4 个 map 存储与三元组$[a_i,a_{i+1},a_{i+2}]$中$a_i,a_{i+1}$相同，$a_i,a_{i+2}$相同，$a_{i+1},a_{i+2}$相同，$a_i,a_{i+1},a_{i+2}$都相同的三元组个数

最后就是按照如图的答案公式求出来即可

但这毕竟是最朴素的 所以喜提最差解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll t,n,z[200001],ans;
map<pair<ll,ll>,ll>a,b,c;
map<tuple<ll,ll,ll>,ll>d;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld",&n);
		ans=0;a.clear();b.clear();c.clear();d.clear();//记得初始化 
		for(int i=1;i<=n;i++)scanf("%lld",&z[i]);
		for(int i=1;i<n-1;i++)
		{
			ans+=a[{z[i],z[i+1]}];
			ans+=b[{z[i],z[i+2]}];
			ans+=c[{z[i+1],z[i+2]}];
			ans-=d[make_tuple(z[i],z[i+1],z[i+2])]*3;
			a[{z[i],z[i+1]}]++;
			b[{z[i],z[i+2]}]++;
			c[{z[i+1],z[i+2]}]++;
			d[make_tuple(z[i],z[i+1],z[i+2])]++; 
		}
		printf("%lld\n",ans);
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
const LL M=1e7;
LL a[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("a.in","r",stdin);
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        LL ans=0;
        unordered_map<LL,LL> mp1, mp2, mp3, mp4;
        for(int i=1;i<=n-2;i++){
            ans+=mp1[a[i]*M + a[i+1]]  
                +mp2[a[i]*M + a[i+2]] 
                +mp3[a[i+1]*M + a[i+2]] 
              -3*mp4[a[i]*M*M + a[i+1]*M + a[i+2]];
            mp1[a[i]*M + a[i+1]]++;
            mp2[a[i]*M + a[i+2]]++;
            mp3[a[i+1]*M + a[i+2]]++;
            mp4[a[i]*M*M + a[i+1]*M + a[i+2]]++;
    }
    cout << ans << "\n";
  }
  return 0;
}