分治

新版题中还没有分治题解，而且旧版题里面分治也貌似是小众做法，那我来水一发吧。

不需要复杂的数据结构，你只需要会一个桶和基本分治套路。

因为 $P$ 是一个排列，所以连号区间等价于 $\max_{i=l}^rP_i-\min_{i=l}^{r}P_i=r-l$。

在解决这种限制条件中含有区间极值的全局区间计数问题时，分治非常有用。

考虑当前分治区间 $[L,R]$,设 $mid$ 为区间中点，把完全包含在 $[L,mid]$,和 $(mid,R]$ 的区间扔到下一层分治去计算。此时就只需要考虑左端点在 $[L,mid]$,右端点在 $(mid,R]$ 的区间了。

设一个需要考虑的区间为 $[l,r]$，设 $m=\max_{i=l}^r P_i$。

第一种情况：

$l,m\in[L,mid];r\in(mid,R]$。

转化等式，有 $\max_{i=l}^{r}P_i+l=\min_{i=l}^rP_i+r$。

考虑对每一个 $l$ 找出一个最大的 $r$ 满足 $\max_{i=mid+1}^r P_i < \max_{i=l}^{mid} P_i$。

这个时候就只需要考虑有多少个 $r’\in(mid,r]$ 满足$\min_{i=mid+1}^{r’}P_i+r=m+l$，开个桶记录一下就行，同时要注意去掉 ${r’‘|\min_{i=l}^{mid}P_i<\min_{i=mid+1}^{r’‘}P_i}$ 的贡献并判一下对应的 $r’‘’=\max_{i=l}^{mid}P_i+l-\min_{i=l}^{mid}P_i$ 是否在范围内。

第二种情况：

$l\in[L,mid];r,m\in(mid,R]$。

可以发现这两种情况加上分治下去处理的区间覆盖了所有区间。

转化等式，有 $\max_{i=l}^{r}P_i-r=\min_{i=l}^rP_i-l$。

处理方法跟上面类似，这里不再赘述。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
#define drep(a,b,c) for(int c(a);c>=(b);--c)
using namespace std;
inline int read()
{
	int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res;
}
typedef long long ll;
const int N=5e4+10,M=1e5+5;
int a[N],n,mn[N],mx[N],cnt[N<<2];ll ans;
inline void Solve(int l,int r)
{
	if(l==r){++ans;return;} int mid=(l+r)>>1;
	mn[mid+1]=a[mid+1];mx[mid+1]=a[mid+1];
	rep(mid+2,r,i)mn[i]=min(mn[i-1],a[i]),mx[i]=max(mx[i-1],a[i]);
	mn[mid]=a[mid];mx[mid]=a[mid];
	drep(mid-1,l,i)mn[i]=min(mn[i+1],a[i]),mx[i]=max(mx[i+1],a[i]);
	int pr=mid+1,ppr=mid+1;drep(mid,l,pl)
	{
		while(pr<=r&&mx[pr]<mx[pl]){++cnt[mn[pr]+pr+M];++pr;}
		while(ppr<pr&&mn[ppr]>mn[pl]){--cnt[mn[ppr]+ppr+M];++ppr;}
		ans+=cnt[mx[pl]+pl+M];int tr=mx[pl]+pl-mn[pl];
		if(mid<tr&&tr<ppr)++ans;
	}
	for(int i=ppr;i<pr;++i)cnt[mn[i]+i+M]=0;
	int pl=mid,ppl=mid;rep(mid+1,r,pr)
	{
		while(pl>=l&&mx[pl]<mx[pr]){++cnt[mn[pl]-pl+M];--pl;}
		while(ppl>pl&&mn[ppl]>mn[pr]){--cnt[mn[ppl]-ppl+M];--ppl;}
		ans+=cnt[mx[pr]-pr+M];int tl=mn[pr]-mx[pr]+pr;
		if(ppl<tl&&tl<=mid)++ans;
	}
	for(int i=ppl;i>pl;--i)cnt[mn[i]-i+M]=0;
	Solve(l,mid);Solve(mid+1,r);
}
int main()
{
	n=read();rep(1,n,i)a[i]=read();
	Solve(1,n);printf("%lld\n",ans);
}

时间复杂度 $O(n\log n)$。