【解题报告】EOJ 3534 笋尖爆炸

发表于 更新于

传送门

$\text{Solution}$

非常毒瘤的题目。

考场上时一看就知道是线段树维护，可能要用矩阵快速幂，然后就不会了。

实际上就是 线段树维护 + 矩阵快速幂。

做这道题需要有一点前置知识，就是 $\text{Fibonacci}$ 数列是可加的 。

具体怎么说呢，就是有一个第一项是 $x$ , 第二项是 $y$ 的 $\text{Fibonacci}$ 数列和另一个第一项是 $z$ , 第二项是 $w$ 的 $\text{Fibonacci}$ 数列。那么这两个数列相加就是一个第一项是 $x + z$ ，第二项是 $y + w$ 的 $\text{Fibonacci}$ 数列。证明什么的就略过了。

接下来我们就可以考虑对每个区间将 $\text{Fibonacci}$ 数列首两项和区间和作为 $\text{tag}$ ，每次修改的话可以叠加。

对于一个操作 $1 \quad x \quad y \quad u \quad v$ 。首先在 $x$ 的位置加上 $u$ , 在 $y$ 的位置加上 $v$ 。然后在之后的位置加入 $u, v$ 。

对于添加 $[L, R]$ ，当前区间 $[l, r]$ 满足 $[l, r]$ 覆盖 $[L, R]$ ，此时标记的是 $l-L+1$ 项之后的 $\text{Fibonacci}$ 数列。需要用矩阵进行预处理。转移矩阵为

快速幂一下，调用的时候把 $F_1$ 和 $F_2$ 的值改掉就会得到相应的 $\text{Fibonacci}$ 数列的项和和。

另外给出的操作中是可能反向的，需要正反两棵线段树。询问的时候需要叠加

步骤比较多，常数比较大，考验码量

$\text{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 400005
#define Modify 998244353
int n, m;
typedef std::pair< long long, long long > pll;
pll Fib(long long F1, long long F2, long long n);
long long calc(long long F1, long long F2, long long n);
class Matrix {
public:
	int r, c;
	long long num[5][5];
	Matrix() { memset(num, 0, sizeof num); }
	Matrix(int r, int c) : r(r), c(c) { memset(num, 0, sizeof num); }
	Matrix(int n) : r(n), c(n) {
		memset(num, 0, sizeof num);
		for (int i = 0; i < n; i++)
			this->num[i][i] = 1;
	}
	long long* operator [] (int x) { return num[x]; }
	friend Matrix operator * (Matrix& a, Matrix& b) {
		Matrix c = Matrix(a.r, b.c);
		for (int i = 0; i < a.r; i++)
			for (int j = 0; j < b.c; j++)
				for (int k = 0; k < a.c; k++)
					(c[i][j] += a[i][k] * b[k][j]) %= Modify;
		return c;
	}
} M[N], E;
class SegmentTree {
private:
	long long Fu[2][N << 2], Fv[2][N << 2], Sum[2][N << 2];
    inline void pushdown(int flag, int o, int l, int r) {
        if (!Fu[flag][o] && !Fv[flag][o]) return;
        int mid = (l + r) >> 1;
        pll tmp = Fib(Fu[flag][o], Fv[flag][o], mid - l + 1);
        (Fu[flag][o << 1] += Fu[flag][o]) %= Modify;
        (Fv[flag][o << 1] += Fv[flag][o]) %= Modify;
        (Fu[flag][o << 1 | 1] += tmp.first) %= Modify;
        (Fv[flag][o << 1 | 1] += tmp.second) %= Modify;
        (Sum[flag][o << 1] += calc(Fu[flag][o], Fv[flag][o], mid - l + 1)) %= Modify;
        (Sum[flag][o << 1 | 1] += calc(tmp.first, tmp.second, r - mid)) %= Modify;
        Fu[flag][o] = Fv[flag][o] = 0;
    }
    inline void pushup(int flag, int o) {
        Sum[flag][o] = (Sum[flag][o << 1] + Sum[flag][o << 1 | 1]) % Modify;
    }
public:
    inline void update(int flag, int o, int l, int r, int L, int R, long long u, long long v) {
        if (l > R || r < L) return;
        if (L <= l && r <= R) {
            pll cur = Fib(u, v, l - L);
            (Fu[flag][o] += cur.first) %= Modify;
            (Fv[flag][o] += cur.second) %= Modify;
            (Sum[flag][o] += calc(cur.first, cur.second, r - l + 1)) %= Modify;  
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(flag, o, l, r);
        update(flag, o << 1, l, mid, L, R, u, v);
        update(flag, o << 1 | 1, mid + 1, r, L, R, u, v);
        pushup(flag, o);
    }
    inline void update(int flag, int o, int l, int r, int p, long long u) {
        if (l > p || r < p) return;
        if (l == r) { (Sum[flag][o] += u) %= Modify; return; }
        int mid = (l + r) >> 1;
        pushdown(flag, o, l, r);
        update(flag, o << 1, l, mid, p, u);
        update(flag, o << 1 | 1, mid + 1, r, p, u);
        pushup(flag, o);
    }
    inline long long query(int flag, int o, int l, int r, int L, int R) {
        if (l > R || r < L) return 0; 
        if (L <= l && r <= R) return Sum[flag][o]; 
        int mid = (l + r) >> 1;
        pushdown(flag, o, l, r); 
        return (query(flag, o << 1, l, mid, L, R) + query(flag, o << 1 | 1, mid + 1, r, L, R)) % Modify;
    }
    inline long long query(int L, int R) {
        return (query(0, 1, 1, n, L, R) + query(1, 1, 1, n, n - R + 1, n - L + 1)) % Modify;
    }
} ST;
inline void init() {
    M[0] = Matrix(3); E = Matrix(3);
    E[0][1] = E[1][2] = E[2][1] = 1, E[2][2] = 0;
    for (int i = 1; i < N; i++)
        M[i] = M[i - 1] * E;
}
pll Fib(long long F1, long long F2, long long n) {
    return std::make_pair((M[n][2][1] * F2 + M[n][2][2] * F1) % Modify, (M[n][1][1] * F2 + M[n][1][2] * F1) % Modify);
}
long long calc(long long F1, long long F2, long long n) {
    return (M[n + 1][0][0] * F1 + M[n + 1][0][1] * F2 + M[n + 1][0][2] * F1 - F1 - F2 + 2 * Modify) % Modify;
}
int main() {
	init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int opt, x, y, u, v;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1) {
            scanf("%d%d", &u, &v);
            int flag = x > y;
            if (flag) {
                x = n - x + 1;
                y = n - y + 1;
            }
            ST.update(flag, 1, 1, n, x, u);
            if (x + 1 <= y) ST.update(flag, 1, 1, n, x + 1, v);
            if (x + 2 <= y) ST.update(flag, 1, 1, n, x + 2, y, u, v);
        }
        else {
            if (x > y) std::swap(x, y); 
            std::cout << ST.query(x, y) << std::endl;
        }
    }
    return 0;
}