分析

首先这道题是可以用的时间复杂度过的
所以我们可以考虑使用数据结构优化一下
所以我们选择可以直接获得区间信息的树状数组
将所有区间按排序之后，依次遍历
将前一个出现当前颜色的
将当前位置即可统计区间答案

代码

//Newcoder 18 B
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(LL i=Head[A];i;i=Next[i])
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MAXN = 1e6 + 100;
int Num[MAXN],Temp[MAXN],last[MAXN],Side,Total,So;
struct Node{int l,r,id;}q[MAXN];
inline bool cmp(Node x,Node y) { return x.r < y.r; }
inline void add(int x,int d){ while(x<=Total)  Temp[x] += d,x+=Lowbit(x); }
inline int ask(int x){ int Res = 0; while(x) Res += Temp[x],x-=Lowbit(x); return Res; }
int main()
{
    scanf("%d",&Total);
    FOR(i,1,Total) scanf("%d",&Num[i]);
    Side = 0;
    FOR(i,1,Total) FOR(j,1,Total) 
        q[++Side].l = i,q[Side].r = j,q[Side].id = Side; 
    sort(q+1,q+1+Side,cmp);
    for(int i = 1,R = 0;i <= Side;i++)
    {
        while(R < q[i].r)
        {
            R++;
            if(!last[Num[R]]) last[Num[R]] = R;
            else {
                add(last[Num[R]],-1);
                last[Num[R]] = R;
            } 
            add(R,1);
        }
        So += ask(q[i].r) - ask(q[i].l-1);
    }
    printf("%d\n",So);
    //system("pause");
    return 0;
}