2021杭电多校2 G I love data structure

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=6967

简要题意：给定两个长度为 $n$ 的序列 $a_i$ 和 $b_i$，现在有 $m$ 次操作，操作有四种：给定区间 $[l,r]$ 和 $v$ 以及一个 $0/1$ 参数表示操作 $a$ 还是 $b$，将 $a$ 或 $b$ 的区间 $[l,r]$ 都加上 $v$；给定区间 $[l,r]$，将 $[l,r]$ 内的 $(a_i,b_i)$ 变成 $(3a_i+2b_i,3a_i-2b_i)$；给定区间 $[l,r]$，将 $[l,r]$ 内的 $(a_i,b_i)$ 变成 $(b_i,a_i)$；给定区间 $[l,r]$，求 $\sum_{i=l}^ra_i\times b_i$

Solution

我们发现操作 $2$ 和操作 $3$ 本质都是将 $a$ 或 $b$ 变成 $xa+yb$，那么我们只需要维护一个标记来记录这东西即可

另外我们能够发现这种标记的合并是遵守矩阵乘法的，所以我们为了方便把这个东西当成矩阵维护，另外将其称为乘法标记

另外就是 $a$ 和 $b$ 的区间加，这个我们分别维护两个标记即可，另外我们将其称为加法标记

显然这两种标记是顺序关系标记，我们规定答案的形式是先乘后加，那么我们思考乘法标记对加法标记的影响

能够发现就是直接按照乘法标记的 $x$ 和 $y$ 直接进行变换成 $x\times adda+y\times addb$

另外为了维护 $\sum ab$，我们需要额外维护 $\sum a$、$\sum b$、$\sum a^2$、$\sum b^2$

#include <iostream>
#define maxn 200010
#define ll long long
using namespace std;

const int p = 1000000007;

int n, m;

ll a[maxn], b[maxn];

struct Matrix {
    static const int n = 2;
    ll a[n][n];

    Matrix() { fill(a[0], a[0] + 4, 0); }

    void setone() { for (int i = 0; i < n; ++i) a[i][i] = 1; }

    friend Matrix operator * (const Matrix &u, const Matrix &v) {
        Matrix w;
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    w.a[i][j] = (w.a[i][j] + u.a[i][k] * v.a[k][j]) % p;
        return w; 
    }
} _;

inline ll F(ll x) { return x * x % p; } 

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    ll a, b, ab, aa, bb, adda, addb;
    Matrix mul;
} T[maxn * 4];
inline void maintain(int i) {
    T[i].a = (T[lc].a + T[rc].a) % p;
    T[i].b = (T[lc].b + T[rc].b) % p;
    T[i].ab = (T[lc].ab + T[rc].ab) % p;
    T[i].aa = (T[lc].aa + T[rc].aa) % p;
    T[i].bb = (T[lc].bb + T[rc].bb) % p;
}

void build(int i, int l, int r) {
    T[i].mul = _; 
    if (l == r) return T[i] = { a[l], b[l], a[l] * b[l] % p, a[l] * a[l] % p, b[l] * b[l] % p, 0, 0, _ }, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i); 
}

inline void Update_v(int i, int l, int r, ll adda, ll addb, Matrix mul) {
    ll a = T[i].a, b = T[i].b, aa = T[i].aa, bb = T[i].bb, ab = T[i].ab;
    
    T[i].a = (mul.a[0][0] * a + mul.a[0][1] * b) % p;
    T[i].b = (mul.a[1][0] * a + mul.a[1][1] * b) % p;
    T[i].aa = (F(mul.a[0][0]) * aa + F(mul.a[0][1]) * bb + 2 * mul.a[0][0] * mul.a[0][1] % p * ab) % p;
    T[i].bb = (F(mul.a[1][0]) * aa + F(mul.a[1][1]) * bb + 2 * mul.a[1][0] * mul.a[1][1] % p * ab) % p;
    T[i].ab = (mul.a[0][0] * mul.a[1][0] % p * aa + mul.a[0][1] * mul.a[1][1] % p * bb + (mul.a[0][0] * mul.a[1][1] + mul.a[0][1] * mul.a[1][0]) % p * ab) % p;

    a = T[i].a; b = T[i].b; aa = T[i].aa; bb = T[i].bb; ab = T[i].ab; 
    T[i].a = (a + (r - l + 1) * adda) % p;
    T[i].b = (b + (r - l + 1) * addb) % p;
    T[i].aa = (aa + 2 * adda * a + F(adda) * (r - l + 1)) % p;
    T[i].bb = (bb + 2 * addb * b + F(addb) * (r - l + 1)) % p;
    T[i].ab = (ab + adda * b + addb * a + adda * addb % p * (r - l + 1)) % p; 
}

inline void Update_tag(int i, int l, int r, ll adda, ll addb, Matrix mul) {
    ll _adda = T[i].adda, _addb = T[i].addb;
    T[i].adda = (mul.a[0][0] * _adda + mul.a[0][1] * _addb) % p;
    T[i].addb = (mul.a[1][0] * _adda + mul.a[1][1] * _addb) % p;
    T[i].mul = mul * T[i].mul;

    T[i].adda = (T[i].adda + adda) % p;
    T[i].addb = (T[i].addb + addb) % p; 
}

inline void pushdown(int i, int l, int r) {
    ll &adda = T[i].adda, &addb = T[i].addb;
    Matrix &mul = T[i].mul; int m = l + r >> 1; 

    Update_v(lc, l, m, adda, addb, mul); Update_tag(lc, l, m, adda, addb, mul);
    Update_v(rc, m + 1, r, adda, addb, mul); Update_tag(rc, m + 1, r, adda, addb, mul);

    adda = addb = 0; 
    mul = _;
}

void update_adda(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update_v(i, l, r, v, 0, _), Update_tag(i, l, r, v, 0, _);
    int m = l + r >> 1; pushdown(i, l, r);
    update_adda(lc, l, m, L, R, v); update_adda(rc, m + 1, r, L, R, v); 
    maintain(i); 
}

void update_addb(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update_v(i, l, r, 0, v, _), Update_tag(i, l, r, 0, v, _);
    int m = l + r >> 1; pushdown(i, l, r);
    update_addb(lc, l, m, L, R, v); update_addb(rc, m + 1, r, L, R, v); 
    maintain(i); 
}

void update_mul(int i, int l, int r, int L, int R, const Matrix &mul) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update_v(i, l, r, 0, 0, mul), Update_tag(i, l, r, 0, 0, mul);
    int m = l + r >> 1; pushdown(i, l, r);
    update_mul(lc, l, m, L, R, mul); update_mul(rc, m + 1, r, L, R, mul); 
    maintain(i); 
}

ll query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].ab;
    int m = l + r >> 1; pushdown(i, l, r); 
    return (query(lc, l, m, L, R) + query(rc, m + 1, r, L, R)) % p; 
}

inline void solve_1() {
    int x, y, z, w; cin >> w >> x >> y >> z; 
    if (!w) update_adda(1, 1, n, x, y, z);
    else update_addb(1, 1, n, x, y, z); 
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    Matrix mul; mul.a[0][0] = 3; mul.a[0][1] = 2; mul.a[1][0] = 3; mul.a[1][1] = -2;
    update_mul(1, 1, n, x, y, mul); 
}

inline void solve_3() {
    int x, y; cin >> x >> y;
    Matrix mul; mul.a[0][1] = mul.a[1][0] = 1; 
    update_mul(1, 1, n, x, y, mul); 
}

inline void solve_4() {
    int x, y; cin >> x >> y;
    cout << (query(1, 1, n, x, y) + p) % p << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; _.setone(); 
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    build(1, 1, n); cin >> m;
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        switch (opt) {
        case 1: solve_1(); break;
        case 2: solve_2(); break;
        case 3: solve_3(); break;
        case 4: solve_4(); break;
        }
    }
    return 0;
}