P11261 [COTS 2018] 直方圖 Histogram
看了這篇題解懂了的，大家也可以去看看。
以及，后來自己想出來了單調(diào)棧解法，看題解里似乎沒有這個解法，所以交一發(fā)題解。
1.笛卡爾樹做法
如果我們確定了 \(x\) 軸上矩形的范圍，那么制約矩陣面積大小的就是這段區(qū)間上 \(h\) 的最小值。
我們假設(shè)當(dāng)前位置是 \(pos\) 的話，這個直方圖局部就長這樣：
這啟發(fā)我們建小根笛卡爾樹，當(dāng)我們走到該位置 \(pos\) 時，我們可以像上述所言枚舉左右端點（當(dāng)然，前提是左右端點必須在 \(pos\) 是最小值的范圍內(nèi)）。設(shè)左右端點為 \(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\) 表示的就是當(dāng)前確定了 \(x\) 軸長度，使它恰好能達到面積要求的 \(y\) 的值。\(y\) 一求出來以后，很顯然 \([y,h_{pos}]\) 都是可以取的縱軸坐標(biāo)值。取 max 是因為這個值可能超過右端點導(dǎo)致此時無解。
然后我們稍微化簡一下這坨式子。
首先，如果想過這個題的話，同時枚舉兩邊是不合適的。所以我們考慮枚舉較小的那一邊（我們欽定是 \(L\) 那一邊）（類似于啟發(fā)式合并，時間復(fù)雜度降為 \(O(n \log n)\)）。這樣的話，為了方便后續(xù)計算，我們換個元，令 \(k=i+j-1\)。
這樣原式子變?yōu)?\(\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}\)。
后面那坨東西又很類似于前綴和，所以我們可以預(yù)處理一個 \(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]內(nèi)的合法矩陣個數(shù)
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.單調(diào)棧做法
單調(diào)棧的做法和笛卡爾樹本質(zhì)上沒什么區(qū)別。都是找這樣的一個邊界，也就是找使得長度最大的 \(l,r\)，滿足 \(\forall i \in [l,r],h_{pos} \le h_{i}\)。
只不過，一個建笛卡爾樹，一個跑兩遍單調(diào)棧。
單調(diào)棧做法有一個注意的地方，就是對于相同高度的處理，必須是一個算進區(qū)間去一個不算進區(qū)間去，這樣就能不重不漏地處理區(qū)間內(nèi)有相同數(shù)字的情況。
反之，如果都算進去，假設(shè) \(h_{pos}=h_{id}\)，那么在統(tǒng)計穿過 \(id\) 的答案時會計算一部分穿過 \(pos\) 的答案，而同理統(tǒng)計穿過 \(pos\) 的答案時會計算一部分穿過 \(id\) 的答案。那答案不就重復(fù)了嗎。
至于推式子部分，單調(diào)棧的式子和笛卡爾樹式子一模一樣。甚至一部分代碼都是我復(fù)制過來的
代碼：
單調(diào)棧
#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前面下標(biāo)最大的、h大小小于等于i的位置
//nxt[i]:i后面下標(biāo)最小的、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;
//為了防止求區(qū)間時出錯，如果它右側(cè)沒有比它小的數(shù)，就令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;
cout<<"i="<<i<<" l="<<l<<" r="<<r<<endl;
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;
}
說起來，笛卡爾樹的建樹過程似乎就仿照了單調(diào)棧呢。也許很多思想是兩者通用的。
如果你覺得本篇題解還不錯的話，不妨點個贊吧 qwq
浙公網(wǎng)安備 33010602011771號