原题链接：G-小红的独特区间
题目大意：给定长度为n的数组，要求求出合法子数组方案数，合法的方案定义是：连续子数组恰好包含三种不同的数字。
思路：先将相同的数字缩成同一个数字，然后对于每一个数字，求出满足合法的区间的长度再计算总和即可。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1e9+7;
ld pi=acos(-1.0);
ll p[N],pre[N];
struct node
{
ll x,sum;
}q[N];
pii op[N];//记录正好为3的区间
int main()
{
ios::sync_with_stdio(NULL);cin.tie(0),cout.tie(0);
ll n;cin>>n;
for(int i=1;i<=n;i++)cin>>p[i];//正常读入
ll cnt=0;
for(int i=1;i<=n;i++)//将连续相同的数字 缩成同一个点，并且用sum来记录数字个数
{
if(p[i]==p[i-1])
{
q[cnt].sum++;
}
else
{
cnt++;
q[cnt].x=p[i];
q[cnt].sum=1;
}
}
ll sum=0;//代表当前枚举的区间几个不同的数据
for(int i=1;i<=cnt;i++)pre[i]=pre[i-1]+q[i].sum;//确定sum等于3的左右区间之后用前缀和来求可以优化复杂度
op[0]={0,0};op[cnt+1]=op[0];
map<ll,ll> st;//记录当前区间的数字
for(int i=1,j=0;i<=cnt;i++)
{
ll l=0,r=0;
st[q[i-1].x]-=q[i-1].sum;//减去前一个数的影响
if(!st[q[i-1].x]&&i>1)sum--;//如果减去前一个之后，st中就没有了前一个数，并且不能是q[0]这个没有意义的，那么代表需要减少一个数
if(sum==3)//如果正好为3，就代表从i到op[i-1].second的区间有三个不同的数字
{//用l和r代表op记录的区间，那么就是从i到l-1有2个不同的数字，从i到r有三个不同的数字
// 因为sum=3，那么r是确定的，但是l是不确定的，那么就从i往后面枚举,因为前面进行了缩点的操作，所以确定l的位置是非常快的
map<ll,bool> ui;
ll jk=i;
for(;jk<=cnt;jk++)
{
ui[q[jk].x]=1;
if(ui.size()==3)break;
}
op[i]={jk,op[i-1].second};//记录
continue;
}
while(sum<=3&&j<=cnt)//如果小于3
{
j++;
if(!st[q[j].x])sum++;//如果当前点还没有记录，那么不同的数+1
st[q[j].x]+=q[j].sum;//每加入一个数就要加入这个点里面的数量
if(sum==3)
{
if(!l)l=j;
r=j;
}
}
st[q[j].x]-=q[j].sum;//j的位置是不合法的要去除
sum--;//如果是因为sum=4，退出循环那么就要减去j这个值的影响，如果j>cnt,0也是新的数字所以也要减去
if(j>cnt)
{
if(sum==3)op[i]={l,r};//到了最后一位，那么就要判断一下是从sum=2的状态到最后一位，还是从sum=3的状态到最后一位
else op[i]={0,0};
}
else
{
op[i]={l,r};//都没到最后就退出，那么一定是满足op的要求的
}
j--;
}
ll ans=0;
for(int i=1;i<=cnt;i++)
{
ll a=q[i].sum,l=op[i].first,r=op[i].second;//因为是连续的子数组并且只能三种数，那么影响方案的就是第一个数的数目和sum=3的范围
ll b=pre[r]-pre[l-1];//前缀和快速求
ans=ans+a*b;
}
cout<<ans<<endl;
return 0;
}