Nick has some permutation consisting of p integers from 1 to n. A
segment [l,?r] (l?≤?r) is a set of elements pi satisfying l?≤?i?≤?r.Nick calls a pair of segments [a0,?a1] and [b0,?b1]
(1?≤?a0?≤?a1?<?b0?≤?b1?≤?n) good if all their (a1?-?a0?+?b1?-?b0?+?2)
elements, when sorted in ascending order, form an arithmetic
progression with a difference of 1. That is, when they sorted in
ascending order, the elements are in the form
{x,?x?+?1,?x?+?2,?…,?x?+?m?-?1}, for some x and m.Your task is to find the number of distinct pairs of good segments in
the given permutation. Two pairs of segments are considered distinct
if the sets of elements contained in these pairs of segments are
distinct. For example, any segment [l,?r] (l?<?r) can be represented
as a pair of segments, as [l,?i] and [i?+?1,?r] (l?≤?i?≤?r). As all
these pairs consist of the same set of elements, they are considered
identical.See the notes accompanying the sample tests for clarification. Input
The first line contains integer n (1?≤?n?≤?3·105) — the permutation
size. The second line contains n space-separated distinct integers pi,
(1?≤?pi?≤?n). OutputPrint a single integer — the number of good pairs of segments of
permutation p.Please, do not use the %lld specifier to read or write 64-bit integers
in С++. It is preferred to use the cin, cout streams or the %I64d
specifier.
考虑枚举数字区间的右端点r，维护i..r这一段数值由几个区间拼成，如果区间数为1或2，则可以累加进答案。
当加入一个数x时，如果i..x这一段中没有数在x旁边【是指在原数列中在x旁边】，相当于新开一个区间，那么区间数会加1。如果恰有一个，相当于拼在另一个区间旁边，区间数不变。如果两个都出现了，相当于合并了两个区间，区间数减1。不难发现，随着左端点i越来越小，加入的数越来越多，“在x旁边的数的个数”是单调变化的。
于是我们需要用一个数据结构，支持区间加1减1，以及询问1和2的个数。于是可以用线段树，记录最小值和次小值及其出现个数【合并的时候注意分类讨论】。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
int a[300010],p[300010],
mn1[4000010],c1[4000010],mn2[4000010],c2[4000010],tag[4000010],
n;
void down(int p)
{if (tag[p]){mn1[p]+=tag[p];mn2[p]+=tag[p];tag[p*2]+=tag[p];tag[p*2+1]+=tag[p];tag[p]=0;}
}
int calc(int x1,int x2,int y1,int y2,int &v,int &c)
{if (x1==x2){v=x1;c=y1+y2;return 0;}if (x1<x2){v=x1;c=y1;return 1;}v=x2;c=y2;return -1;
}
void up(int p)
{down(p);down(p*2);down(p*2+1);switch (calc(mn1[p*2],mn1[p*2+1],c1[p*2],c1[p*2+1],mn1[p],c1[p])){case 0:calc(mn2[p*2],mn2[p*2+1],c2[p*2],c2[p*2+1],mn2[p],c2[p]);break;case 1:calc(mn2[p*2],mn1[p*2+1],c2[p*2],c1[p*2+1],mn2[p],c2[p]);break;case -1:calc(mn1[p*2],mn2[p*2+1],c1[p*2],c2[p*2+1],mn2[p],c2[p]);break;}
}
void add(int p,int L,int R,int l,int r,int x)
{down(p);if (L==l&&r==R){tag[p]+=x;return;}int mid=(L+R)/2;if (r<=mid) add(p*2,L,mid,l,r,x);else{if (l>mid) add(p*2+1,mid+1,R,l,r,x);else{add(p*2,L,mid,l,mid,x);add(p*2+1,mid+1,R,mid+1,r,x);}}up(p);
}
int qry(int p,int L,int R,int l,int r)
{down(p);int ret=0;if (L==l&&r==R){if (mn1[p]<=2) ret+=c1[p];if (mn2[p]<=2) ret+=c2[p];return ret;}int mid=(L+R)/2;if (r<=mid) return qry(p*2,L,mid,l,r);if (l>mid) return qry(p*2+1,mid+1,R,l,r);return qry(p*2,L,mid,l,mid)+qry(p*2+1,mid+1,R,mid+1,r);
}
void in(int p,int L,int R,int x)
{if (L==R){mn1[p]=0;c1[p]=1;return;}down(p);int mid=(L+R)/2;if (x<=mid) in(p*2,L,mid,x);else in(p*2+1,mid+1,R,x);up(p);
}
int main()
{int i,j,k,q,x,y,z;LL ans=0;scanf("%d",&n);for (i=1;i<=n;i++)scanf("%d",&a[i]);for (i=1;i<=n;i++)p[a[i]]=i;memset(mn1,0x3f,sizeof(mn1));memset(mn2,0x3f,sizeof(mn2));for (i=1;i<=n;i++){in(1,1,n,i);x=p[i]==1?n+1:a[p[i]-1];y=p[i]==n?n+1:a[p[i]+1];if (x<y) swap(x,y);if (y>i) add(1,1,n,1,i,1);else{if (x>i) add(1,1,n,y+1,i,1);else{add(1,1,n,x+1,i,1);add(1,1,n,1,y,-1);}}ans+=qry(1,1,n,1,i);}printf("%I64d\n",ans-n);
}