B. Forming Triangles

map

可以理解成一个简单的数组，只是下标可以变成Key,也就是所谓的索引

通过向 map 中插入一个类型为 pair<Key, T> 的值可以达到插入元素的目的，例如

mp.insert(pair<string,int>("Alan",100));

erase(key) 函数会删除键为 key 的 所有 元素。返回值为删除元素的数量。

erase(pos): 删除迭代器为 pos 的元素，要求迭代器必须合法。

erase(first,last): 删除迭代器在 [first,last) 范围内的所有元素。

clear() 函数会清空整个容器。

一般情况下推荐使用 find() 函数来寻找特定键的元素。

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin>>t;
	
	while(t--)
	{
		int n;
		cin>>n;
		
		map<int,int> mp;
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			++mp[x];
		}
		
		long long res=0;
		int sum=0;
		for(auto it:mp)
		{
			long long cnt=it.second;
			if(cnt>=3)
				res+=cnt*(cnt-1)*(cnt-2)/6;
			if(cnt>=2)
				res+=cnt*(cnt-1)/2*sum;
			sum+=cnt;
		}
		cout<<res<<endl;
	}
	
	return 0;
}

注意该题n的数据范围是3e5

也就是说遍历三层循环求解妥妥超时

刚开始还以为是什么神奇的算法

结果发现是2的次方的问题，假设一条边严格大于另一条边，长度至少是另一条边的两倍，假设有三条边，a,b,c，长度依次递减，并且是严格递减，那么a至少是b的两倍，b至少是c的两倍，那么b+c一定严格小于a，难以构成三角形

假设b不严格大于c，假设b=c,a严格大于b，那么还是不满足要求，因为取一个极端情况，a刚好是 b的两倍，那么b+c=a

所以只有可能出现 a=b>=c，可以使得三条边可以构成三角形

假设三条边都相等，可以使用组合数来求解答案

从所有相等的边里面选3条边可以构成一个三角形，假设该长度的出现次数是7，那么答案就是，$$C_7^3$$,(把数学公式打出来还挺难的，还得学，做题挺难的，还得练)

假设有两条边相等，也就是一个等腰三角形，那么底一定要严格小于腰（不严格小于就是等边三角形，上面已经考虑过了）

假设腰的长度的出现次数等于7，$$C_7^2$$表示选择两个相等的腰，然后再乘以严格小于腰的长度的边出现的次数即可

严格小于腰的长度的边的出现的次数用sum来进行保存

因为是从小到大遍历的map里面的元素，所以保证了严格小于

用map的索引表示边的长度，map的第二个变量表示的是该长度的边出现的次数

最后输出答案即可