「题解」Fancy Fence

打了一场 CEOI2020 Day1 的线上镜像，发现这个 A 题好像有点水啊，于是切掉，来水个题解……

原题链接

容易发现，一个长为 $N$ 宽为 $M$ 的矩形的合法子矩形的数量可以 $O(1)$ 算。具体来讲，设：
$$A=\dbinom{NM}{2}, B = M·\dbinom{N}{2},C=N·\dbinom{M}{2}$$ 有该矩形的子矩形数量为：
$$(A-B-C)/2+B+C$$ 之所以要算的这么麻烦是为了去重…这个重复的问题考场上卡了我半小时/kk…

那么考虑对于每个 $h_i$ 拆开来算贡献。对于当前的高度 $h_i$ ，我们确定两个端点 $l_i$ 和 $r_i$，使得 $[l_i,r_i]$ 是极长的一段区间满足 $\min\limits_{l_i\le k\le r_i} h_k=h_i$，于是我们可以找到一个极大的矩形，然后就可以在这个矩形里面算答案了。

剩下的问题是考虑重复，即这个矩形下方存在一个 $h$ 更小的矩形（它应该是矮矮长长的这个样子），而它的贡献我们已经在前面算过了。我们强制令矩形的一个端点在这个矩形上方就好了。

于是就只剩下单调栈的复杂度了，总复杂度 $O(n)$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;

#define int long long // 惨痛经历

const int P = 1e9 + 7;
const int CN = 2e5 + 5;
const int i2 = 500000004;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

int n, h[CN], w[CN], sum[CN], pr[CN], nt[CN], stk[CN], top = 0, ans = 0; 
map<int, bool> cal[CN];

int C(int x) {return (1ll * x * (x - 1) / 2ll) % P;}
int calc(int l, int a, int b){
    int ab = ((a - b) % P + P) % P;
    int rec = C(1ll * l * ab % P), t1 = C(ab), t2 = C(l);
    t1 = 1ll * t1 * l % P, t2 = 1ll * t2 * ab % P;
    rec = ((rec - t1 - t2) % P + P) % P, rec = 1ll * rec * i2 % P;
    rec = (rec + t1 + t2) % P;
    int t = C(l + 1); t = 1ll * t * b % P, t = 1ll * t * ab % P, t = (t + P) % P;
    return (rec + t) % P;
}

signed main()
{
    freopen("_in.in", "r", stdin);

    n = read();
    for(int i = 1; i <= n; i++) h[i] = read();
    for(int i = 1; i <= n; i++) w[i] = read(), sum[i] = (sum[i - 1] + w[i]) % P, ans = (1ll * w[i] * h[i] % P + ans) % P;

    stk[++top] = 1, pr[1] = 0;
    for(int i = 2; i <= n; i++){
        while(h[ stk[top] ] >= h[i]) top--;
        pr[i] = stk[top], stk[++top] = i;
    }
    stk[top = 1] = n + 1;
    for(int i = n; i; i--){
        while(h[ stk[top] ] >= h[i]) top--;
        nt[i] = stk[top], stk[++top] = i;
    }

    for(int i = 1; i <= n; i++){
        if(cal[ pr[i] ][ h[i] ]) continue; cal[ pr[i] ][ h[i] ] = true;
        int l = (sum[ nt[i] - 1 ] - sum[ pr[i] ] + P) % P, a = h[i], b = max(h[ pr[i] ], h[ nt[i] ]);
        ans = (ans + calc(l, a, b)) % P;
    }

    printf("%lld", ans);
}