CF1849E - Max to the Right of Min

题目传送门

单调栈，启发式分裂，ad-hoc。

题意

给定一个排列，求有多少个子数组满足最小值的下标小于最大值的下标。（\(n\le10^6\)）
题解

这题乍一看没有什么思路，想了想DP还不好转移，总结了一下发现是因为确定不了枚举顺序。
所以我们改变枚举策略，每次计算 \(a_i\) 作为区间最大值对答案的贡献。
先看看暴力怎么做，首先设 \([l,r]\) 是 \(a_i\) 作为区间最大值的最大区间，那么我们可以枚举子数组的左端点，维护 \([l,i)\) 的最小值 \(mn\)，计算其对答案的贡献，由于我们发现在左端点固定的情况下，符合条件的右端点是一段前缀区间，而边界就是右边第一个小于 \(mn\) 的位置。时间复杂度是 \(O(n^2)\) 的。
上面的东西都可以用单调栈维护。
考虑优化，我们发现上面的算法是枚举左端点，并对右端点统计答案，显然我们反过来，枚举右端点，并对左端点统计答案也是可以的。
这里注意到两边的枚举次数之和等于区间长度，于是我们考虑哪侧短就枚举哪侧，这样子单次枚举复杂度最多是区间长度的一半，我们将其叫做「启发式分裂」。
下面算一下时间复杂度，我们建出笛卡尔树，那么时间复杂度就是每个点较小的子树的大小之和，也就是 \(T(n)=2T(n)+O(\frac n 2)=O(n \log n)\)。
代码

[code]#include #define int long longusing namespace std;const int N=1e6+5;const int INF=1e18;int n,ans;int st[N],top;int a[N],lmx[N],rmx[N],lmn[N],rmn[N];void calc1(int l,int x,int r){    int mn=INF,y;    for(int i=x-1;i>=l;i--){        if(mn>a){            mn=a;            y=rmn;        }        ans+=min(y,r)-x+1;    }}void calc2(int l,int x,int r){      int mn=INF,y;    ans+=x-l;//右端点为 x 时单独计算。    for(int i=x+1;ia){            mn=a;            y=lmn-1;        }        ans+=max(y-l+1,0LL);    }}signed main(){    cin.tie(nullptr)->sync_with_stdio(false);    cin>>n;    for(int i=1;i>a;    st[top=0]=0,a[0]=INF;    for(int i=1;i=1;i--){        while(a[st[top]]>a) top--;        rmn=st[top]-1;        st[++top]=i;    }    for(int i=1;i