博客

这类找区间个数题，一般可以枚举一个端点，找符合条件的另一个端点的个数。

这题我们枚举右端点，对每个数x而言，其作为右端点的时候，满足条件的左端点必须是其前面2个x与前面3个x之间的点。

我们用lst[i][j],当前状态下，从后往前第j个i的位置。

显然：对于每个值i，都有：在区间[lst[i][3]+1 – lst[i][2]] 合法，其余点做为左端点均不合法。

由此有了做法：

从左往右枚举右端点，对于每个值，当前状态下，某个点可以作为左端点，则其值+1，否则不变。

显然，只有满足点值为0的点才是符合条件的左端点。

我们枚举右端点的同时不断改变每个点的值，始终保持对每个值，不在[lst[i][3]+1 – lst[i][2]] 的点的值均加1.

然后求出最小值是否为0，及最小值的个数，就是满足条件的左端点的个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
const double PI= acos(-1.0);
const int M = 5e5+7;
ll tr[M<<2],nm[M<<2],tg[M<<2];
int lst[M][5],a[M];
void pu(int o)
{
	tr[ls]+=tg[o];tg[ls]+=tg[o];
	tr[rs]+=tg[o];tg[rs]+=tg[o];
	tg[o]=0;
} 
void bd(int o,int l,int r)
{
	if(l==r)
	{
		nm[o]=1;
		return ;
	}
	int m=(l+r)/2;
	bd(ls,l,m);
	bd(rs,m+1,r);
}
void up(int o,int l,int r,int x,int y,int d)//区间加法
{
	if(x<=l&&r<=y)
	{
		tr[o]+=d;
		tg[o]+=d;
		return ;
	}
	pu(o);
	int m=(l+r)/2;
	if(x<=m)up(ls,l,m,x,y,d);
	if(y>m)up(rs,m+1,r,x,y,d); 
	tr[o]=min(tr[ls],tr[rs]);
	if(tr[ls]<tr[rs])nm[o]=nm[ls];
	else if(tr[ls]>tr[rs])nm[o]=nm[rs];
	else nm[o]=nm[ls]+nm[rs];
} 
struct node{
	ll x,nm;
};
const int inf = 1e7;
node qu(int o,int l,int r,int x,int y)//区间值为0的个数 
{
	if(x<=l&&r<=y)
	{
		return node{tr[o],nm[o]};
	}
	pu(o); 
	int m=(l+r)/2;
	node tp={inf,0},a={inf,0},b={inf,0};
	if(x<=m)a=qu(ls,l,m,x,y);
	if(y>m)b=qu(rs,m+1,r,x,y); 
	tp.x=min(a.x,b.x);
	if(a.x<b.x)tp.nm=a.nm;
	else if(a.x>b.x)tp.nm=b.nm;
	else tp.nm=a.nm+b.nm;
	return tp;
}
int main()
{
	ios::sync_with_stdio(false);
  	cin.tie(0);
  	int n;
  	cin>>n;
  	for(int i=1;i<=n;i++)cin>>a[i];
  	ll ans=0;
  	bd(1,1,n);
  	for(int i=1;i<=n;i++)
  	{
  		up(1,1,n,lst[a[i]][1]+1,i,1);
  		if(lst[a[i]][3]+1<=lst[a[i]][2])up(1,1,n,lst[a[i]][3]+1,lst[a[i]][2],-1);
  		if(lst[a[i]][4]+1<=lst[a[i]][3])up(1,1,n,lst[a[i]][4]+1,lst[a[i]][3],1);
		node tp=qu(1,1,n,1,i);
//		cout<<i<<" - -  ";
//		for(int j=1;j<=n;j++)
//		{
//			node t=qu(1,1,n,j,j);
//			cout<<t.x<<" ";
//		}
//		cout<<endl;
//  		cout<<i<<" ："<<tp.x<< " "<<tp.nm<<endl;
  		if(tp.x==0)ans+=tp.nm ;
  		lst[a[i]][4]=lst[a[i]][3];
  		lst[a[i]][3]=lst[a[i]][2];
		lst[a[i]][2]=lst[a[i]][1];
		lst[a[i]][1]=i; 
	}
	cout<<ans<<endl;
	return 0;
}