【单调栈】P6801 [CEOI 2020] 花式围栏

__S08577__ · 2025-11-04 17:14:19 · 个人记录

个人认为细节很多，且不好想出来。

题意

给定每个矩形的宽度和高度，求里面有多少个子矩形。

思路

不妨考虑用单调栈维护（这里很难考虑到），最后我们处理单调递增的矩形肯定是好处理的，这里最后再说。

我们设栈顶的矩形高度为 h1，要加入的矩形的高度为 h2，栈顶下面的矩形高度为 h3，当 h1 \leq h2 时，显然直接加入即可，否则，我们将 h1 削到 \max(h2,h3) 的高度，计算被削掉矩形的贡献即可。

现在，我们主要的问题就是计算被削掉矩形的贡献。考虑贡献即为只有 4个点都在削掉的矩形里面 或者 只有2个点在削掉的矩形里面的矩形个数。

这个如何计算呢，不妨考虑容斥，只需要将整个矩形里面的子矩形个数减去被删去的矩形中子矩形的个数。

不难发现，高度为 h，宽度为 w 的矩形中子矩形的个数为 \frac{h\times (h+1)}{2} \times \frac{w\times (w+1)}{2} 个。

最后，我们还要加入一个高度为0的矩形，目的是为了将单调栈清空。

步骤见下图：

int f(int x){
    return (x*(x+1)/2)%mod;
}

signed main(){

//   freopen("a.in","r",stdin);
//   freopen("a.out","w",stdout);
    fst
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++) cin>>w[i];
    int ans=0;
    st.push(0);
    for(int i=1;i<=n+1;i++){
        int d=st.top();
        int sum=0;
        while(h[i]<h[st.top()]){
            d=st.top();
            st.pop();
            (sum+=w[d])%=mod;
            (ans+=(f(h[d])-f(max(h[st.top()],h[i]))+mod%mod)*f(sum)%mod)%=mod;
        }
        (w[i]+=sum)%=mod;
        st.push(i);
    }
    cout<<(ans+mod)%mod;
    return 0;
}