思路与算法

化简Cij=(Ai+i)(Bj+j)，两因子均为正，任意k方块最大值等于对应行段最大值乘列段最大值，所以F[k]为两数组所有k窗口最大值之和的乘积。单调栈分配相等值归属，得到每个元素向左L、向右R的主导范围。令x=min(L,R),y=max(L,R)，它在长度k窗口的出现数依次为k、x、L+R-k；对这三段用斜率/截距差分加权，一次扫描求全部k。

正确性说明

每个窗口按固定相等值规则唯一选出其最大元素。包含该位置的窗口左右扩展数受L,R限制，按长度计数得到三段梯形函数，因此差分求出的每个窗口和精确。正外积把二维最大化独立为行列两部分，所有行列窗口组合求和满足分配律，乘积即答案。

复杂度

两数组读入、栈、差分初始化和扫描均O(N)，每个位置常数次进出栈及区间差分，总O(N)时间、O(N)空间。乘法取模前使用64位。

易错点

先把下标i,j加到Ai,Bj；否则外积模型不成立。相等值一侧严格一侧非严格，避免重复归属。负斜率差分最终需归一化到非负余数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
vector<long long> calc(vector<long long> a) {
    int n = a.size();
    vector<int> L(n), R(n), st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.back()] <= a[i])
            st.pop_back();
        L[i] = i - (st.empty() ? -1 : st.back());
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.back()] < a[i])
            st.pop_back();
        R[i] = (st.empty() ? n : st.back()) - i;
        st.push_back(i);
    }
    vector<long long> da(n + 3), db(n + 3), v(n + 1);
    auto add = [&](int l, int r, long long slope, long long base) {
        if (l > r)
            return;
        da[l] = (da[l] + slope) % MOD;
        da[r + 1] = (da[r + 1] - slope) % MOD;
        db[l] = (db[l] + base) % MOD;
        db[r + 1] = (db[r + 1] - base) % MOD;
    };
    for (int i = 0; i < n; i++) {
        int x = min(L[i], R[i]), y = max(L[i], R[i]);
        add(1, x, a[i], 0);
        add(x + 1, y, 0, a[i] * x);
        add(y + 1, x + y - 1, -a[i], a[i] * (x + y));
    }
    long long x = 0, y = 0;
    for (int k = 1; k <= n; k++) {
        x = (x + da[k]) % MOD;
        y = (y + db[k]) % MOD;
        v[k] = ((x * k + y) % MOD + MOD) % MOD;
    }
    return v;
}
int main() {
    int n;
    cin >> n;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] += i + 1;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i] += i + 1;
    }
    auto x = calc(a), y = calc(b);
    for (int k = 1; k <= n; k++)
        cout << x[k] * y[k] % MOD << (k == n ? '\n' : ' ');
}