说实话这题挺简单的（知道题解以后），但是一般人做的时候脑洞不大一点还不一定做得出来。 显然，题目可化简为：给定 N 个数的一个排列，问这个序列中有多少个子区间的数恰好是连续的。 进一步可以化为：有多少种情况使得，相邻的 k 个数中最大值和最小值的差小于等于 k-1。 大致有两种解法，一种是分治，一种是线段树。 这里主要讲一下分治的解法。 考虑分治，对于当前区间[L,R]，记区间中点为 mid。当前区间的答案就是Ans[L..mid]+Ans[mid+1..R]+跨过中点的合法区间数，然后就分为两种情况了： 1.最小值和最大值在同侧。 2.最小值和最大值在异侧。 下面只考虑最值同在左，和最小值在左，最大值在右的情况。 因为其余两种是对称的。 对于最值同在左侧的情况，我们O(N)枚举左边界在哪，然后可以 计算出右边界的位置，在判断是否合法，统计答案。对于最小值在左侧，最大值在右侧的情况，如果一个区间满足我们所要求的关系的话，就一定有： max(a[mid +1]…a[right]) - min(a[left]…a[mid]) =right- left 移项可得 max(a[mid +1]…a[right]) - right = min(a[left]…a[mid]) -left 然后可以用单调栈来完成这个任务。 如果加一些黑科技可以大大减少代码量，但是复杂度会多一个 log。 简单提一下，线段树解法的思路大致也是维护一个单调栈，然后进行区间修改和查询，统计答案。 蒟蒻还在用Pas，虽然偶尔也用C艹
uses math; const maxn=300010; var n,i,j,k,p,m,x:longint; maxm,minm,num:array[0..maxn]of longint; f:array[0..maxn shl 1]of longint; ans:longint; procedure fz(l,r:longint); var mid,i,j,l1,r1:longint; begin mid:=(l+r)>>1; minm[mid]:=num[mid]; maxm[mid]:=num[mid]; maxm[mid+1]:=num[mid+1]; minm[mid+1]:=num[mid+1]; for i:=mid+2 to r do begin maxm[i]:=max(num[i],maxm[i-1]); minm[i]:=min(num[i],minm[i-1]); end; for i:=mid-1 downto l do begin maxm[i]:=max(num[i],maxm[i+1]); minm[i]:=min(num[i],minm[i+1]); end; for i:=mid downto l do begin r1:=i+maxm[i]-minm[i]; if (r1>mid)and(r1<=r)and(minm[r1]>minm[i])and(maxm[r1]<maxm[i]) then inc(ans); end; for i:=mid+1 to r do begin l1:=i-maxm[i]+minm[i]; if (l1>=l)and(l1<=mid)and(minm[l1]>minm[i])and(maxm[l1]<maxm[i])then inc(ans); end; l1:=mid+1; r1:=l1; for i:=mid downto l do begin while (r1<=r)and(minm[r1]>minm[i])do begin inc(f[maxm[r1]-r1+n]); inc(r1); end; while(l1<r1)and(maxm[l1]<maxm[i])do begin dec(f[maxm[l1]-l1+n]); inc(l1); end; inc(ans,f[minm[i]-i+n]); end; for i:=l1 to r1-1 do dec(f[maxm[i]-i+n]); l1:=mid; r1:=l1; for i:=mid+1 to r do begin while (l1>=l)and(minm[l1]>minm[i])do begin inc(f[maxm[l1]+l1]); dec(l1); end; while (r1>l1)and(maxm[r1]<maxm[i])do begin dec(f[maxm[r1]+r1]); dec(r1); end; inc(ans,f[minm[i]+i]); end; for i:=r1 downto l1+1 do dec(f[maxm[i]+i]); if (l<r)then begin fz(l,mid); fz(mid+1,r); end; end; begin read(n); for i:=1 to n do begin read(x,num[x]); end; fz(1,n); writeln(ans+n); end.