The 2021 ICPC Asia Nanjing Regional Contest E.Paimon Segment Tree 区间合并线段树/维护矩阵乘法

The 2021 ICPC Asia Nanjing Regional Contest E.Paimon Segment Tree 区间合并线段树/维护矩阵乘法

题目大意

给定长度为的序列，要求支持区间加操作，同时对操作记录历史版本，查询问区间操作中的每个数的平方之和。

题目思路

推了一会，发现线段树合并硬写很凌乱，然后队友告诉是线段树维护矩阵乘法，那么就考虑怎么维护：

设：

• ，区间长度
• ，区间和
• ，区间平方和
• ，区间历史平方和

考虑每次区间加，那么考虑各个数字的变化：

• 对于区间和，变化量就是
• 对于区间平方和：
  

那么就有：

把上面的式子整理一下，就可以用矩阵乘法维护，转移矩阵：

看了看题解，说“设置了一个让不需要任何矩乘优化就可勉强通过的时限”，说明有卡常？

但并没有卡到（

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10, MOD = 1e9 + 7;
int a[N], ans[N];

namespace ffastIO {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}

using ffastIO::read;

struct Mat{
    static const int M = 4;
    int v[M][M];
    Mat() { memset(v ,0 ,sizeof(v)); }
    Mat(int k){
        v[0][0] = v[1][1] = v[2][2] = v[3][3] = v[2][3] = 1;
        v[0][1] = k;
        v[0][2] = v[0][3] = k * k % MOD;
        v[1][2] = v[1][3] = 2 * k % MOD;
        v[1][0] = v[2][0] = v[2][1] = v[3][0] = v[3][1] = v[3][2] = 0;
    }
    void eye() { for(int i = 0; i < M; i++) for(int j = 0; j < M; j++) v[i][j] = (i == j); }
    int * operator [] (int x) { return v[x]; }
    const int *operator [] (int x) const { return v[x]; }
    Mat operator * (const Mat& B) {
        const Mat &A = *this;
        Mat ret;
        for(int k = 0; k < M; k++){
            for(int i = 0; i < M; i++)
                for(int j = 0; j < M; j++){
                    ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
        return ret;
    }
    Mat operator + (const Mat& B) {
        const Mat &A = *this;
        Mat ret;
        for(int i = 0; i < M; i++)
            for(int j = 0; j < M; j++)
                ret[i][j] = (A[i][j] + B[i][j]) % MOD;
        return ret;
    }
    Mat pow(int n) const {
        Mat A = *this, ret; ret.eye();
        for(; n; n >>= 1, A = A * A) if(n & 1) ret = ret * A;
        return ret;
    }
};

namespace SegTree{
    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l,
    #define rson rs, mid + 1,
    struct Info{
        int val[4];
        Info () {}
        Info (int x){ val[0] = 1, val[1] = x, val[2] = val[3] = x * x % MOD; }
        Info operator+ (Info b){ 
            Info res;
            for(int i = 0; i < 4; i++){ res.val[i] = (val[i] + b.val[i]) % MOD; } 
            return res; 
        }
        Info operator* (Mat b){
            int res[4] = {0, 0, 0, 0};
            for(int i = 0; i < 4; i++){
                for(int j = 0; j < 4; j++) res[j] = (res[j] + val[i] * b[i][j]) % MOD;
            }
            for(int i = 0; i < 4; i++) val[i] = res[i];
            return *this;
        }
    } tree[N << 2];

    Mat lazy[N << 2];

    inline void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }

    inline void push(int rt, Mat k){ tree[rt] = tree[rt] * k, lazy[rt] = lazy[rt] * k; }

    inline void push_down(int rt){
        push(ls, lazy[rt]), push(rs, lazy[rt]);
        lazy[rt].eye();
    }

    void build(int rt, int l, int r){
        lazy[rt].eye();
        if(l == r) return (void)(tree[rt] = Info(a[l]));
        int mid = l + r >> 1;
        build(lson), build(rson);
        push_up(rt);
    }

    void update(int rt, int l, int r, int L, int R, int val){
        if(r < L || l > R || (l >= L && r <= R)) return push(rt, Mat((l >= L && r <= R) * val));
        push_down(rt);
        int mid = l + r >> 1;
        update(lson, L, R, val), update(rson, L, R, val);
        push_up(rt);
    }

    Info query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tree[rt];
        push_down(rt);
        int mid = l + r >> 1;
        if(mid >= L && mid < R) return query(lson, L, R) + query(rson, L, R);
        if(mid >= L) return query(lson, L, R);
        if(mid < R) return query(rson, L, R);
        return Info(1);
    }
}

struct modify{ int l, r, val; }op[N];
struct query{ 
    int op, id, x, l, r;
    const bool operator< (const query &s) const { return x < s.x; } 
}que[N];

#define SEGRG 1, 1,

inline void solve(){
    int n = read(), m = read(), q = read();
    for(int i = 1; i <= n; i++) a[i] = (read() + MOD) % MOD;
    SegTree::build(1, 1, n);
    for(int i = 1; i <= m; i++) op[i] = {read(), read(), (read() + MOD) % MOD};
    for(int i = 1; i <= q; i++){
        int l = read(), r = read(), x = read(), y = read();
        que[i * 2 - 1] = query{-1, i, x - 1, l, r};
        que[i * 2] = query{1, i, y, l, r};
    }
    sort(que + 1, que + 1 + 2 * q);
    int now = 1; // while(now <= 2 * q && que[now].x == -1) now++;
    for(; now <= 2 * q && que[now].x == -1; now++);
    for(int i = 0; i <= m; i++){
        if(i) SegTree::update(SEGRG, op[i].l, op[i].r, op[i].val);
        for(; now <= 2 * q && que[now].x == i; now++){
            ans[que[now].id] += que[now].op * SegTree::query(SEGRG, que[now].l, que[now].r).val[3] % MOD;
        }
            
    }
    for(int i = 1; i <= q; i++) printf("%d\n", (ans[i] + MOD) % MOD);
}


signed main(){
    solve();
    return 0;
}