找这道题是因为这是学校模拟赛的题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目连接：GO
题目标签：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目大意：
给出 n(1≤n≤3000)n(1\le n \le 3000)n(1≤n≤3000) 个数 an(1≤ai≤n)a_n(1\le a_i \le n)an (1≤ai ≤n)，计算满足条件 (i<j<k<l)(i<j<k<l)(i<j<k<l) 并且 ai=ak,aj=ala_i=a_k,a_j=a_lai =ak ,aj =al 的四元组 (i,j,k,l)(i,j,k,l)(i,j,k,l) 的个数。
题目解析：
如果直接暴力枚举每个数，O(n4)O(n^4)O(n4)，超时。
注意到 1≤ai≤n≤30001\le a_i\le n\le 30001≤ai ≤n≤3000，那我们考虑前缀和，定义 s(i,j)=∑k=1i1ak=js(i,j) = \sum_{k=1}^i \mathbf{1}_{a_k = j}s(i,j)=∑k=1i 1ak =j ，即前 iii 个数中 =j=j=j 的数的个数。
接下来我们要考虑枚举哪两个数。
i,j 这样无法确定 k,lk,lk,l 的前后关系
i,k 还需要用 vectorvectorvector 维护颜色，否则是 O(n3)O(n^3)O(n3)，较麻烦。
i,l 无法确定 j,kj,kj,k 的前后关系
j,k 此时可能的 iii 为 s(j−1,a(k))s(j-1,a(k))s(j−1,a(k))，可能的 lll 为 s(n,a(j))−s(k,(aj))s(n,a(j))-s(k,(a_j))s(n,a(j))−s(k,(aj ))，根据乘法原理，答案应增加 s(j−1,a(k))×s(n,a(j))−s(k,(aj))s(j-1,a(k))\times s(n,a(j))-s(k,(a_j))s(j−1,a(k))×s(n,a(j))−s(k,(aj ))。
答案记得开 long long
时间复杂度：O(n2)O(n^2)O(n2)
