[CSP-S2019 江西] 和积和

· · 题解

[CSP-S2019 江西] 和积和

发现题目是求所有子区间的和的积的和。

那么就分两条路可走，一个是数学的推导，一个就是暴力维护。

虽然是道黄题，但是我盯真了很久也没发现什么规律，那么就直接维护了吧。

先把柿子拆开，发现就是这样的：

a_1\times b_1+(a_1+a_2)\times (b_1+b_2)+\dots+(a_1+\dots+a_n)\times (b_1+\dots+b_n)+a_2\times b_2+\dots+(a_2+\dots+a_n)\times (b_2+\dots+b_n)+\dots+a_n\times b_n

不难发现这和前缀加脱不了关系。

那么考虑去维护两个序列 A 和 B。

初始 A,B 每个位置都为 0。

先枚举原序列的每个位置，设当前下标为 i。

那么把 A 序列的 1\sim i 全部加上 a_i，B 序列的 1\sim i 全部加上 b_i。

然后把 \sum_{j=1}^{i}A_j\times B_j 累加进答案。

会发现，这样做只有一个区间加，和区间查询，用线段树维护即可。

具体地可以看代码。

suma 代表 A 序列的区间和。

sumb 代表 B 序列的区间和。

mul 代表 \sum_{i=l}^r A_i\times B_i。

#include <bits/stdc++.h>
#define int long long
#define ls k << 1
#define rs k << 1 | 1
#define mid ((l + r) >> 1)

void Freopen() {
    freopen("", "r", stdin);
    freopen("", "w", stdout);
}

using namespace std;
const int N = 5e5 + 10, M = 2e5 + 10, inf = 1e9, mod = 1e9 + 7;

int read( int x = 0) { return cin >> x, x; }

int n;

int a[N], b[N];
int suma[N * 4], sumb[N * 4], mul[N * 4], lya[N * 4], lyb[N * 4];

void pushtaga( int k, int l, int r, int v) {
    suma[k] = (suma[k] + v * (r - l + 1) % mod) % mod;
    lya[k] = (lya[k] + v) % mod;
    mul[k] = (mul[k] + v * sumb[k] % mod) % mod;
}

void pushtagb( int k, int l, int r, int v) {
    sumb[k] = (sumb[k] + v * (r - l + 1) % mod) % mod;
    lyb[k] = (lyb[k] + v) % mod;
    mul[k] = (mul[k] + v * suma[k] % mod) % mod;    
}

void pushdowna( int k, int l, int r) {
    if (! lya[k]) return ;

    pushtaga(ls, l, mid, lya[k]), pushtaga(rs, mid + 1, r, lya[k]);
    lya[k] = 0;
}

void pushdownb( int k, int l, int r) {
    if (! lyb[k]) return ;

    pushtagb(ls, l, mid, lyb[k]), pushtagb(rs, mid + 1, r, lyb[k]);
    lyb[k] = 0;
}

void pushup( int k) {
    suma[k] = (suma[ls] + suma[rs]) % mod;
    sumb[k] = (sumb[ls] + sumb[rs]) % mod;
    mul[k] = (mul[ls] + mul[rs]) % mod;
}

void upda( int x, int y, int v, int k = 1, int l = 1, int r = n) {
    if (x <= l && r <= y) return pushtaga(k, l, r, v), void();

    pushdowna(k, l, r);

    if (x <= mid) upda(x, y, v, ls, l, mid);
    if (y > mid) upda(x, y, v, rs, mid + 1, r);

    pushup(k);
}

void updb( int x, int y, int v, int k = 1, int l = 1, int r = n) {
    if (x <= l && r <= y) return pushtagb(k, l, r, v), void();

    pushdownb(k, l, r);

    if (x <= mid) updb(x, y, v, ls, l, mid);
    if (y > mid) updb(x, y, v, rs, mid + 1, r);

    pushup(k);
}

int ask( int x, int y, int k = 1, int l = 1, int r = n) {
    if (x <= l && r <= y) return mul[k];

    pushdowna(k, l, r), pushdownb(k, l, r);
    int res = 0;

    if (x <= mid) res = (res + ask(x, y, ls, l, mid)) % mod;
    if (y > mid) res = (res + ask(x, y, rs, mid + 1, r)) % mod;

    return res;
}

signed main() {
    ios :: sync_with_stdio(false);

    n = read();

    for ( int i = 1; i <= n; i ++) a[i] = read();
    for ( int i = 1; i <= n; i ++) b[i] = read();

    int ans = 0;

    for ( int i = 1; i <= n; i ++) {
        upda(1, i, a[i]), updb(1, i, b[i]);

        ans = (ans + ask(1, i)) % mod;
    }

    cout << ans;
}