题意：给一个2n的矩阵，每一个点有一个权值，从左上角出发，时间t=0开始，连续的走，将矩阵走完，每走一步，t++,并且得到t当前格子的权值的值，问如何走，使得最走完得到的最大权值和是多少。
不难发现方案一定是先走一个S形，再直着走到头，再走回来。
图片说明 

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
typedef long long ll;
ll a[maxn], b[maxn];
ll sum[maxn][2], Lsum[maxn][2], Rsum[maxn][2];
ll dp[maxn][2];
ll res[maxn];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        sum[i][0] = sum[i - 1][0] + a[i];
        Lsum[i][0] = Lsum[i - 1][0] + i * a[i];
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
        sum[i][1] = sum[i - 1][1] + b[i];
        Lsum[i][1] = Lsum[i - 1][1] + i * b[i];
    }
    for (int i = n; i >= 1; i--) {
        Rsum[i][0] = Rsum[i + 1][0] + (n - i + 1) * a[i];
        Rsum[i][1] = Rsum[i + 1][1] + (n - i + 1) * b[i];
    }
    int cnt = 0;
    for (int i = 1; i <= n; i += 2) {
        dp[i][0] = cnt++; dp[i][1] = cnt++;
        dp[i + 1][1] = cnt++; dp[i + 1][0] = cnt++;
    }

    for (int i = 1; i <= n; i++) {
        res[dp[i][0]] = dp[i][0] * a[i];
        res[dp[i][1]] = dp[i][1] * b[i];
    }
    for (int i = 1; i <= 2 * n; i++) {
        res[i] += res[i - 1];
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dp[i][0] % 2 == 0) {
            ll s1 = sum[n][0] - sum[i - 1][0];
            ll s2 = Lsum[n][0] - Lsum[i - 1][0];
            ll tmp1 = 0, tmp2 = 0; 
            if (i >= dp[i][0]) {
                tmp1 = s2 - s1 * (i - dp[i][0]);
            } else {
                tmp1 = s2 + s1 * (dp[i][0] - i);
            }
            ll s4 = sum[n][1] - sum[i - 1][1];
            ll s5 = Rsum[i][1] - Rsum[n + 1][1];
            ll x = dp[i][0] + (n - i);
            tmp2 = s5 + s4 * x;
            ans = max(ans, tmp1 + tmp2 + (!dp[i][0] ? 0 : res[dp[i][0] - 1]));
//            cout << i << " " << ans << endl;
        }
        if (dp[i][1] % 2 == 0) {
            ll s1 = sum[n][1] - sum[i - 1][1];
            ll s2 = Lsum[n][1] - Lsum[i - 1][1];
            ll tmp1 = 0, tmp2 = 0; 
            if (i >= dp[i][1]) {
                tmp1 = s2 - s1 * (i - dp[i][1]);
            } else {
                tmp1 = s2 + s1 * (dp[i][1] - i);
            }
            ll s4 = sum[n][0] - sum[i - 1][0];
            ll s5 = Rsum[i][0] - Rsum[n + 1][0];
            ll x = dp[i][1] + (n - i);
            tmp2 = s5 + s4 * x;
            ans = max(ans, tmp1 + tmp2 + (!dp[i][1] ? 0 : res[dp[i][1] - 1]));
//            cout << i << " " << ans << endl;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

给你一个长度为n的整形数组a,和m次询问
对于每次询问：输出S(l, r, k)的值。

S(l, r, k) = a[l] * k + a[l + 1] * (k + 1) + a[l + 2] * (k + 2) .... + a[r]*(r - l + k)

1 <= n, m, a[i], k <= 1e6