题目传送门
数学、计数类。
题意
在 \(n\) 个同一底线上宽 \(w\)，高 \(h\)，给定的相邻矩形中，数出在方格上的任意形状的小矩形的个数。
\(1\leq n\leq 10^5,1\leq w,h \leq 10^9\)
题解
我们规定竖直方向上为高，水平方向上为的宽。
要研究 \(n\) 个，就要先研究一个。
我们考察在一个长为 \(h\) ,高为 \(w\) 的矩形中有多少个小矩形（区分位置）。
首先一个小矩形可以被分解成高和宽相乘，也就是说想求小矩形的个数，可以先求出有多少种 \(1 \times x\) 的矩形， \(x \times 1\) 同理。
显然只有一维的话两个边界就可以确定，选择两条边，即可框出一种可能。方案数是 \(\frac {(x+1)x} {2}\) 种。
由此可知小矩形的个数是 \(\frac {h(h+1)w(w+1)} {4}\) 个。
现在回到题目，要我们求n个矩形种总共有多少个矩形，我们刚才已经求出来了单个矩形里的数量，这是一类，现在我们要求贯穿多个矩形的小矩形个数。
朴素的想法是枚举矩形的左右端分别在哪个矩形上，再枚举高度，显然要取这段区间内最短的高度，设最低的高度为 \(H\) ，左右端分别在 \(l,r\) 矩形上 \((l \neq r)\)，因为水平方向上只于
两端矩形宽度有关，于是总数有：
再枚举左右端点，于是有：
时间复杂度 \(O(n^2)\) ，需要优化。
在优化带有求和的式子时，一种常用的思维方式就是更换枚举对象和拆解贡献，我们发现枚举两端不好优化，并且又注意到 \(H\) 很多时候都是相同且连续的，所以我们可以尝试在 \(H\) 上下功夫。
把 \(H\) 写出来：
我们尝试枚举每一个 \(h_i\) 对答案的贡献，首先要知道在哪些区间 \([l,r]\) 内 \(H\) 取到了 \(h_i\) （显然不可能断开），于是我们想要知道满足要求一个最大的区间 \([L,R]\) ，也就是 \(L,R\) 最多能往外走多少，这显然是一个单调栈可以解决的，预处理出数组 L[i] 和 R[i] 。
有了这些我们可以尝试枚举 \(i\) ，计算 \(h_i\) 对答案的贡献，第一件事要把式子写出来：
提项看看：
到这里就豁然开朗了，两个 \(\sum\) 再也不用枚举了，直接前缀和维护就可以了，计算复杂度 \(O(1)\) 。
所以答案就是： \(\sum_{i=1}^{n} ans_i\) 啦！
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
const int inv2=500000004;
const int inv4=250000002;
int n,ans;
int h[N],w[N],sw[N],q[N],t,L[N],R[N];
void pre(){for(int i=1;i<=n;i++){while(t&&h[q[t]]>=h[i]) t--;L[i]=q[t];q[++t]=i;}t=0;for(int i=n;i>=1;i--){while(t&&h[q[t]]>h[i]) t--;if(t==0) R[i]=n+1;else R[i]=q[t];q[++t]=i;}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>h[i];for(int i=1;i<=n;i++) cin>>w[i],sw[i]=sw[i-1]+w[i];for(int i=1;i<=n;i++) ans=(ans+h[i]*(h[i]+1)%mod*w[i]%mod*(w[i]+1)%mod*inv4%mod)%mod;pre();for(int i=1;i<=n;i++){if(R[i]-L[i]<=2) continue;int wl=(sw[i]-sw[L[i]]+mod)%mod,wr=(sw[R[i]-1]-sw[i-1]+mod)%mod;ans=(ans+h[i]*(h[i]+1)%mod*inv2%mod*wl%mod*wr%mod)%mod;ans=(ans-h[i]*(h[i]+1)%mod*inv2%mod*w[i]%mod*w[i]%mod+mod)%mod;}cout<<ans;return 0;
}