CF193D Two Segments

$\color{deeppink}link$

$n$ 阶排列，选两个连续子序列，使得子序列中的元素在值域上是连续的一段区间，求方案数（元素集相同视为同一序列）。

考虑在值域上找，更直观且不重复。

转化下条件，即使在值域上选一段区间，使得这些值的位置只能有小于等于 $2$ 段。

考虑从小到大加入数 $i$，维护每个值作为左端点的数到 $i$ 要的连通块个数。

先将 $i$ 单独视为一个连通块，将 $i$ 加入时，每个值的连通块个数都要 $+1$。

然后考虑合并掉 $i$ 左右的连通块。显然，当 $i$ 在原序列左或右边的数已被加入时，他会合并掉一个，这样值小于等于这个数（是 $i$ 旁边的数）的连通块个数 $-1$。

用一个权值线段树维护区间中的最小值、次小值以及他们的方案数，每次就查询小于等于 $2$ 的连通块个数即可。

还有就是次小值是最小值 $+1$（如果有的话）。

时间是 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+50;

int n,mi[N],val[N][2],la[N],a[N],p[N];long long ans;

#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)

void down(int x)
{
	if(!la[x])return;
	la[ls]+=la[x];
	la[rs]+=la[x];
	mi[ls]+=la[x];
	mi[rs]+=la[x];
	la[x]=0;
}

void up(int x)
{
	mi[x]=min(mi[ls],mi[rs]);val[x][0]=val[x][1]=0;
	if(mi[ls]==mi[x])val[x][0]+=val[ls][0],val[x][1]+=val[ls][1];
	if(mi[rs]==mi[x])val[x][0]+=val[rs][0],val[x][1]+=val[rs][1];
	if(mi[ls]==mi[rs]+1)val[x][1]+=val[ls][0];
	if(mi[rs]==mi[ls]+1)val[x][1]+=val[rs][0];
}

void insert(int x,int l,int r,int d)
{
	if(l==r)return (void)(mi[x]=1,val[x][0]=1);
	down(x);if(d<=mid)insert(ls,l,mid,d);
	else insert(rs,mid+1,r,d);
	up(x);
}

void del(int x,int l,int r,int d)
{
	if(d>=r)return (void)(la[x]--,mi[x]--);
	down(x);del(ls,l,mid,d);
	if(mid+1<=d)del(rs,mid+1,r,d);
	up(x);
}

main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],p[a[i]]=i;memset(mi,127,sizeof mi);
	insert(1,1,n,1);a[0]=a[n+1]=1919810;
	for(int i=2;i<=n;i++)
	{
		++la[1],++mi[1];
		if(a[p[i]+1]<i)del(1,1,n,a[p[i]+1]);
		if(a[p[i]-1]<i)del(1,1,n,a[p[i]-1]);
		if(mi[1]==1)ans+=val[1][0]+val[1][1];
		if(mi[1]==2)ans+=val[1][0];
		insert(1,1,n,i);
	}
	cout<<ans;
	
}