P11261 [COTS 2018] 直方图 Histogram

看了这篇题解懂了的，大家也可以去看看。

以及，后来自己想出来了单调栈解法，看题解里似乎没有这个解法，所以交一发题解。

---

题目传送门

欢迎光临我的博客

1.笛卡尔树做法

如果我们确定了 \(x\) 轴上矩形的范围，那么制约矩阵面积大小的就是这段区间上 \(h\) 的最小值。

我们假设当前位置是 \(pos\) 的话，这个直方图局部就长这样：

这启发我们建小根笛卡尔树，当我们走到该位置 \(pos\) 时，我们可以像上述所言枚举左右端点（当然，前提是左右端点必须在 \(pos\) 是最小值的范围内）。设左右端点为 \(l,r\)。

这样的话，再记\(L=pos-l+1,R=r-pos+1\)，那么 \(pos\) 对答案的贡献就是 \(\sum\limits_{i=1}^{L}{\sum\limits_{j=1}^{R}{\max(h_{pos}- \lceil \frac{p}{i+j-1} \rceil + 1 , 0)}}\)。

这坨式子还是很好懂的。我们枚举的 \(i,j\) 都是指包含了 pos 点位的、向左/右又延伸了几位。这样计算的话中心点位被算了两遍，所以要减一。

\(\lceil \frac{p}{i+j-1} \rceil\) 表示的就是当前确定了 \(x\) 轴长度，使它恰好能达到面积要求的 \(y\) 的值。\(y\) 一求出来以后，很显然 \([y,h_{pos}]\) 都是可以取的纵轴坐标值。取 max 是因为这个值可能超过右端点导致此时无解。

然后我们稍微化简一下这坨式子。

首先，如果想过这个题的话，同时枚举两边是不合适的。所以我们考虑枚举较小的那一边（我们钦定是 \(L\) 那一边）（类似于启发式合并，时间复杂度降为 \(O(n \log n)\)）。这样的话，为了方便后续计算，我们换个元，令 \(k=i+j-1\)。

这样原式子变为 \(\sum\limits_{i=1}^{L}{\sum\limits_{k=i}^{i+R-1}{\max(h_{pos}- \lceil \frac{p}{k} \rceil + 1 , 0)}}\)。

其次我们考虑如何脱掉外面的 max。如果 \(h_{pos}- \lceil \frac{p}{k} \rceil + 1 \le 0\)，显然它不会对答案有任何贡献。所以我们考虑找出一个最小的 \(q\)，使得 \(h_{pos}- \lceil \frac{p}{q} \rceil + 1 > 1\)。

显然 \(q=\lceil \frac{p}{h_{pos}} \rceil\)，原式子化简为 \(\sum\limits_{i=1}^{L}{\sum\limits_{k=\max(i,q)}^{i+R-1}{h_{pos}- \lceil \frac{p}{k} \rceil + 1}}\)。

最后，由于我们是在特定的 \(pos\) 下考虑的，所以我们可以把第二层 \(\Sigma\) 拆开，拆成 \(((i+R-1)-\max(i,q)+1)(h_{pos}+1)-\sum\limits_{k=\max(i,q)}^{i+R-1}{\lceil \frac{p}{k} \rceil}\)。

后面那坨东西又很类似于前缀和，所以我们可以预处理一个 \(sum_i\) 表示 \(\lceil \frac{p}{1} \rceil + \lceil \frac{p}{2} \rceil + \cdots + \lceil \frac{p}{i} \rceil\)。

综上，原式 \(= \sum\limits_{i=1}^{L}{[((i+R-1)-\max(i,q)+1)(h_{pos}+1)-(sum_{i+R-1}-sum_{\max(i,q)-1})]}\)。

然后我们正常递归求答案即可。

笛卡尔树

#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();}while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}const int N=1e5+5;
int n,p,h[N],ls[N],rs[N],root,sum[N];
stack<int> st;inline int f(int l,int r,int h){//同题解，这里l=max(i,q),r=i+R-1 if(l>r) return 0;return (r-l+1)*(h+1)-(sum[r]-sum[l-1]);
}inline void build(){//用栈建笛卡尔树 for(int i=1;i<=n;i++){int lst=0;while(!st.empty()&&h[st.top()]>h[i]){lst=st.top();st.pop();}if(!st.empty()){int u=st.top();ls[i]=rs[u];rs[u]=i;}else{ls[i]=lst;}st.push(i);}
}inline int query(int id,int l,int r){//用于求所有左右端点在[l,r]内的合法矩阵个数 if(!id) return 0;int ans=0;int q1=query(ls[id],l,id-1);//两端点落在id左边的情况 ans+=q1;int q2=query(rs[id],id+1,r);//两端点落在id右边的情况 ans+=q2;int L=id-l+1,R=r-id+1;if(L>R){swap(L,R);}for(int i=1;i<=L;i++){//穿过id位置的情况 ans+=f(max(i,(p-1)/h[id]+1),i+R-1,h[id]);}return ans;
}signed main(){n=read(),p=read();for(int i=1;i<=N-5;i++){sum[i]=sum[i-1]+(p-1)/i+1;}for(int i=1;i<=n;i++){h[i]=read();}build();while(!st.empty()){root=st.top();st.pop();}int ans=query(root,1,n);printf("%lld",ans);return 0;
}

大家写这个东西的时候一定要保持清醒，并且要搞明白这个东西的含义。

2.单调栈做法

单调栈的做法和笛卡尔树本质上没什么区别。它俩的不同之处就是如何找某个位置 \(pos\) 的边界，即使得长度最大的 \(l,r\)，满足 \(\forall i \in [l,r],h_{pos} \le h_{i}\) 且该区间内不存在一个 \(i\) 使得 \(h_{i}=h_{pos}\)。相当于保证 \(pos\) 是严格的最小值。

为什么要保证 \(pos\) 是严格的最小值呢？假如区间内有一个 \(id\) 满足 \(h_{pos}=h_{id}\)，那么你在统计穿过 \(id\) 的答案时会计算一部分穿过 \(pos\) 的答案，而同理统计穿过 \(pos\) 的答案时会计算一部分穿过 \(id\) 的答案。那答案不就重复了吗。

至于推式子部分，单调栈的式子和笛卡尔树式子一模一样。甚至一部分代码都是我复制过来的

代码：

单调栈

#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();}while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}const int N=1e5+5;
int n,p,h[N],pre[N],nxt[N],sum[N];
//pre[i]:i前面下标最大的、h大小小于等于i的位置
//nxt[i]:i后面下标最小的、h大小小于等于i的位置
stack<int> st;inline int f(int l,int r,int h){if(l>r) return 0;return (r-l+1)*(h+1)-(sum[r]-sum[l-1]);
}signed main(){n=read(),p=read();for(int i=1;i<=N-5;i++){sum[i]=sum[i-1]+(p-1)/i+1;}for(int i=1;i<=n;i++){h[i]=read();}for(int i=n;i>=1;i--){while(!st.empty()&&h[st.top()]>=h[i]){st.pop();}if(!st.empty()){nxt[i]=st.top();}else{nxt[i]=n+1;//为了防止求区间时出错，如果它右侧没有比它小的数，就令nxt[i]=n+1 }st.push(i);} while(!st.empty()) st.pop();//求两次栈要清空 for(int i=1;i<=n;i++){while(!st.empty()&&h[st.top()]>h[i]){st.pop();}if(!st.empty()){pre[i]=st.top();}st.push(i);}int ans=0;//几乎同单调栈解法 for(int i=1;i<=n;i++){int l=pre[i]+1,r=nxt[i]-1;int L=i-l+1,R=r-i+1;if(L>R) swap(L,R);for(int j=1;j<=L;j++){ans+=f(max(j,(p-1)/h[i]+1),j+R-1,h[i]);} }printf("%lld",ans);return 0;
}

说起来，笛卡尔树的建树过程似乎就仿照了单调栈呢。也许很多思想是两者通用的。

如果你觉得本篇题解还不错的话，不妨点个赞吧 qwq