CF1849E - Max to the Right of Min
题目传送门单调栈，启发式分裂，ad-hoc。
题意
给定一个排列，求有多少个子数组满足最小值的下标小于最大值的下标。（\(n\le10^6\)）
题解
这题乍一看没有什么思路，想了想DP还不好转移，总结了一下发现是因为确定不了枚举顺序。
所以我们改变枚举策略，每次计算 \(a_i\) 作为区间最大值对答案的贡献。
先看看暴力怎么做，首先设 \(\) 是 \(a_i\) 作为区间最大值的最大区间，那么我们可以枚举子数组的左端点，维护 \([l,i)\) 的最小值 \(mn\)，计算其对答案的贡献，由于我们发现在左端点固定的情况下，符合条件的右端点是一段前缀区间，而边界就是右边第一个小于 \(mn\) 的位置。时间复杂度是 \(O(n^2)\) 的。
上面的东西都可以用单调栈维护。
考虑优化，我们发现上面的算法是枚举左端点，并对右端点统计答案，显然我们反过来，枚举右端点，并对左端点统计答案也是可以的。
这里注意到两边的枚举次数之和等于区间长度，于是我们考虑哪侧短就枚举哪侧，这样子单次枚举复杂度最多是区间长度的一半，我们将其叫做「启发式分裂」。
下面算一下时间复杂度，我们建出笛卡尔树，那么时间复杂度就是每个点较小的子树的大小之和，也就是 \(T(n)=2T(n)+O(\frac n 2)=O(n \log n)\)。
代码
#include #define int long longusing namespace std;const int N=1e6+5;const int INF=1e18;int n,ans;int st,top;int a,lmx,rmx,lmn,rmn;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=0,a=INF; for(int i=1;i=1;i--){ while(a]>a) top--; rmn=st-1; st[++top]=i; } for(int i=1;i 前排留名，哈哈哈 很好很强大我过来先占个楼 待编辑 谢谢分享，试用一下 这个有用。 谢谢分享，辛苦了 分享、互助 让互联网精神温暖你我 谢谢楼主提供！ 用心讨论，共获提升！ 懂技术并乐意极积无私分享的人越来越少。珍惜 鼓励转贴优秀软件安全工具和文档！ 这个有用。 前排留名，哈哈哈 鼓励转贴优秀软件安全工具和文档！ 过来提前占个楼 这个好，看起来很实用 东西不错很实用谢谢分享 分享、互助 让互联网精神温暖你我 谢谢分享，辛苦了 分享、互助 让互联网精神温暖你我
页:
[1]
2