#include <bits/stdc++.h>
using namespace std;

int b[3100];
long long ans;
map<int,int> a[3100];
map<int,int>::iterator p;

int main()
{
	

	
int n,m,i,j,k,x,y,z,s1=0;
cin>>m;
for (k=1;k<=m;k++)
	{
	cin>>n;
	for (i=1;i<=n;i++)scanf("%d",&b[i]);
	for (i=1;i<=n+1;i++)a[i].clear();
	for (i=2;i<=n+1;i++)
		{
		for (p=a[i-1].begin();p!=a[i-1].end();p++)
			{
			x=(*p).first;
			y=(*p).second;
			a[i][x]=y;
			}
		x=b[i-1];
		a[i][x]++;		
		}
	ans=0;
	for (i=2;i<=n;i++)
		for (j=i+1;j<=n-1;j++)
			{
			x=b[i];
			y=b[j];
			ans=ans+((long long)a[i][y]*(a[n+1][x]-a[j+1][x]));
			}
	cout<<ans<<endl;
	for (i=1;i<=n;i++)s1=s1+a[i].size();

	}


return 0;
}

我开了一个这样的map，在碰上极端数据m=1;n=3000;b[i]=i的数据，map用size累加，算出map中值为8991003个。可实际使用空间居然达到了412.5MB 而且，一个n^2logn的算法，在n=3000时时间达到了12秒。

请问有哪位大佬能帮我看看为什么会这样？

原题在原题 （请各位善良的管理员不要屏蔽我，我不是在宣传网站）