牛牛的等差数列（树状数组，区间加等差数列、区间求和）

标签：牛牛 sum cin int add 区间 ll 等差数列

https://ac.nowcoder.com/acm/contest/5157/C

区间加等差数列，区间求和

树状数组，二阶差分

\(b_i = a_i-a_{i-1}\)

\(c_i=b_i-b_{i-1}\)

\[\sum_{i=1}^n a_i = \sum_{i=1}^n \sum_{j=1}^i b_j = \sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j c_k \\= \sum_{k=1}^n c_k \sum_{i,j}[k\le j\le i\le n] = \sum_{k=1}^n c_k \frac{(1+n-k+1)(n-k+1)}{2} \\= \frac12 \times \left [(n+1)(n+2)\sum_{k=1}^n c_k - (2n+3)\sum_{k=1}^n kc_k + \sum_{k=1}^n k^2c_k \right] \]

在原数组 \(a[]\) 的 \([l,r]\) 区间加一个首项为 \(a_0\) 公差为 \(d\) 的等差数列

就是 b[l] += a0, b[l+1~r] += d, b[r+1] -= a0 + d(n-1)

就是 c[l] += a0, c[l+1] += d-a0, c[r+1] -= a0+d*n, c[r+2] += a0+d(n-1)

关于取模：取所有可能的模数的乘积作为模数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 3*5*7*11*13*17*19*23;
const int inv2 = 55773218; //2的逆，我本地暴力找的

struct BIT {
    int n; vector<ll> tr;
    BIT(int n): n(n), tr(n + 1) {}
    int lowbit(int x) { return x & -x; }
    void add(int p, ll x) { for (; p <= n; p += lowbit(p)) (tr[p] += x) %= P; }
    ll ask(int p) { ll s = 0; for (; p > 0; p -= lowbit(p)) s += tr[p]; return s % P; }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    BIT c(n), kc(n), kkc(n);
    auto add = [&](int p, ll x) { //对c数组的单点加
        c.add(p, x); kc.add(p, x * p % P); kkc.add(p, x * p % P * p % P);
    };
    auto upd = [&](int l, int r, ll a, ll d) { //a数组区间加等差数列
        add(l, a);
        add(l + 1, d - a);
        add(r + 1, -(a + d * (r - l + 1) % P));
        add(r + 2, (a + d * (r - l)) % P);
    };
    auto ask = [&](int n) {
        ll s = c.ask(n) * (n + 1) % P * (n + 2) % P;
        s -= (2 * n + 3) * kc.ask(n) % P;
        s += kkc.ask(n);
        return s % P * inv2 % P;
    };
    
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        upd(i, i, x, 0);
    }
    
    int q;
    cin >> q;
    while (q--) {
        int o, l, r, a, d, m;
        cin >> o;
        if (o == 1) {
            cin >> l >> r >> a >> d;
            upd(l, r, a, d);
        } else {
            cin >> l >> r >> m;
            ll ans = (ask(r) - ask(l - 1)) % m;
            cout << (ans + m) % m << '\n';
        }
    }
    
    return 0;
}

标签：牛牛,sum,cin,int,add,区间,ll,等差数列
From： https://www.cnblogs.com/wushansinger/p/18010870