ABC246Ex 01? Queries Solution

ABC246Ex 01? Queries Solution更好的阅读体验戳此进入浅谈 DDP 与广义矩阵乘法（戳此进入）引入例题 #1广义矩阵乘法DDP例题 #0例题 #0.5例题 #1例题 #2例题 #3UPD

更好的阅读体验戳此进入

这题的题解是从我写的 Blog 中截出来的，可以直接去看原 Blog。

浅谈 DDP 与广义矩阵乘法（戳此进入）

引入

例题 #1

题目 SP1043 GSS1 - Can you answer these queries I。

$a_n$ $q$ $\left[ l_i, r_i \right]$ 的区间最大子段和。

$1 \le n \le 5 \times 10^4, a_i \le 15007$ $q$ 在 int 范围内。

$dp(i)$ $a_i$ $\left[ 1, i \right]$ 的最大子段和。

$dp(i) = \max(dp(i - 1) + a_i, a_i)$ ，对于本题则为：

\begin{matrix} d p (i) = {\begin{cases} a_{i} & i = l \\ max (d p (i - 1) + a_{i}, a_{i}) & l < i \leq r \end{cases} \end{matrix}

但是每次询问都重新维护一遍显然会寄，所以考虑一些人类智慧。

广义矩阵乘法

首先对于普通的矩阵乘法，我们随便举个例子：

[\begin{matrix} a & b \\ c & d \end{matrix}] [\begin{matrix} e \\ f \end{matrix}] = [\begin{matrix} a e + b f \\ c e + d f \end{matrix}]

我们考虑把这玩意省略的东西写全一点：

[\begin{matrix} a & b \\ c & d \end{matrix}] [\begin{matrix} e \\ f \end{matrix}] = [\begin{matrix} a \times e + b \times f \\ c \times e + d \times f \end{matrix}]

$+$ $\times$ $\oplus$ $\otimes$ ，替换一下就是：

[\begin{matrix} a & b \\ c & d \end{matrix}] [\begin{matrix} e \\ f \end{matrix}] = [\begin{matrix} a \otimes e \oplus b \otimes f \\ c \otimes e \oplus d \otimes f \end{matrix}]

这就是广义矩阵乘法了。

然后为了让这东西能有点用，所以现在我们还需要让广义矩阵乘法具有结合律，也就是：

A (B C) = (A B) C

或者写成：

(A (B C))_{i, j} = ((A B) C)_{i, j}

展开一下有：

\begin{aligned} (A (B C))_{i, j} & = ⨁_{k = 1}^{p} A_{i, p} \otimes (B C)_{p, j} \\ = ⨁_{k = 1}^{p} (A_{i, p} \otimes (⨁_{s = 1}^{q} B_{p, s} \otimes C_{s, j})) \end{aligned}

\begin{aligned} ((A B) C)_{i, j} & = ⨁_{s = 1}^{q} (A B)_{i, s} \otimes C_{s, j} \\ = ⨁_{s = 1}^{q} ((⨁_{k = 1}^{p} A_{i, k} \otimes B_{k, p}) \otimes C_{s, j}) \end{aligned}

$\otimes$ $\oplus$ $(a \oplus b) \otimes c = (a \otimes c) \oplus (b \otimes c)$ ，那么把上面的两个式子拆开之后，最后就会发现实际上是相同的。

$\otimes$ $\oplus$ 存在分配律，那么形成的广义矩阵乘法矩阵之间就满足结合律。

DDP

为了便于理解，我们先引入一个更简单的例子。

例题 #0

题面：求斐波那契数列。

$dp(i) = dp(i - 1) + dp(i - 2)$ 。

我们考虑一些~~让复杂度更高~~奇妙的方法。

$X$ $0$ $dp(i - 1)$ $0$ ，则有：

\begin{matrix} X [\begin{matrix} d p (i - 1) \\ d p (i - 2) \end{matrix}] = [\begin{matrix} d p (i) \\ 0 \end{matrix}] \end{matrix}

$\otimes$ $\times$ $\oplus$ $+$ $X$ 为：

\begin{matrix} X = [\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}] \end{matrix}

也就是说：

[\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}] [\begin{matrix} d p (i - 1) \\ d p (i - 2) \end{matrix}] = [\begin{matrix} d p (i) \\ 0 \end{matrix}]

$\texttt{LHS}$ $dp$ 的式子接着拆下去：

\begin{matrix} X [\begin{matrix} d p (i - 2) \\ d p (i - 3) \end{matrix}] = [\begin{matrix} d p (i - 1) \\ d p (i - 2) \end{matrix}] \end{matrix}

$0$ $dp(i - 1)$ $0$ 也是可以转移的，只是会更复杂一些）。所以我们最开始的式子就变成了：

\begin{matrix} X [\begin{matrix} d p (i - 1) \\ d p (i - 2) \end{matrix}] = [\begin{matrix} d p (i) \\ d p (i - 1) \end{matrix}] \end{matrix}

$X$ 了：

[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} d p (i - 1) \\ d p (i - 2) \end{matrix}] = [\begin{matrix} d p (i) \\ d p (i - 1) \end{matrix}]

然后我们继续往下转移：

[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} d p (i - 2) \\ d p (i - 3) \end{matrix}] = [\begin{matrix} d p (i) \\ d p (i - 1) \end{matrix}]

此时我们便能发现一些奇妙的推导：

{[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}]}^{i - 3} [\begin{matrix} d p (2) \\ d p (1) \end{matrix}] = [\begin{matrix} d p (i) \\ d p (i - 1) \end{matrix}]

$\log$ 求了（虽然常数大了点）。

当然这只是最最基础的 DDP。

例题 #0.5

题目：LG-P1115 最大子段和。

$dp(i)$ $a_i$ $\left[ 1, i \right]$ $dp(i) = \max(dp(i - 1) + a_i, a_i)$ $\max$ $ans(i) = \max(dp(i), ans(i - 1))$ 。于是我们不难推出如下转移：

[\begin{matrix} a n s (i - 1) & d p (i - 1) & 0 \end{matrix}] [\begin{matrix} 0 & - \infty & - \infty \\ a_{i} & a_{i} & - \infty \\ a_{i} & a_{i} & 0 \end{matrix}] = [\begin{matrix} a n s (i) & d p (i) & 0 \end{matrix}]

$\otimes$ $+$ $\oplus$ $\max$ $+$ $\max$ 有分配律，则矩阵有结合律。

然后像之前一样拆下去就可以得到一大串矩阵相乘，~~成功大幅增加常数~~成功提高了转移的扩展性。

例题 #1

现在让我们回到文章伊始提到的例题，这里我们再回顾一下：

题目 SP1043 GSS1 - Can you answer these queries I。

$a_n$ $q$ $\left[ l_i, r_i \right]$ 的区间最大子段和。

$1 \le n \le 5 \times 10^4, a_i \le 15007$ $q$ 在 int 范围内。

$dp(i)$ $a_i$ $\left[ 1, i \right]$ 的最大子段和。

$dp(i) = \max(dp(i - 1) + a_i, a_i)$ ，对于本题则为：

\begin{matrix} d p (i) = {\begin{cases} a_{i} & i = l \\ max (d p (i - 1) + a_{i}, a_{i}) & l < i \leq r \end{cases} \end{matrix}

和上一题一样，我们还是考虑令：

\begin{matrix} a n s (i) = {\begin{cases} d p (i) & i = l \\ max (a n s (i - 1), d p (i)) & l < i \leq r \end{cases} \end{matrix}

$i = l$ $l \lt i \le r$ 的式子变成广义矩乘：

[\begin{matrix} a n s (i - 1) & d p (i - 1) & 0 \end{matrix}] [\begin{matrix} 0 & - \infty & - \infty \\ a_{i} & a_{i} & - \infty \\ a_{i} & a_{i} & 0 \end{matrix}] = [\begin{matrix} a n s (i) & d p (i) & 0 \end{matrix}]

然后继续往下拆：

[\begin{matrix} a n s (i - 2) & d p (i - 2) & 0 \end{matrix}] [\begin{matrix} 0 & - \infty & - \infty \\ a_{i - 1} & a_{i - 1} & - \infty \\ a_{i - 1} & a_{i - 1} & 0 \end{matrix}] [\begin{matrix} 0 & - \infty & - \infty \\ a_{i} & a_{i} & - \infty \\ a_{i} & a_{i} & 0 \end{matrix}] = [\begin{matrix} a n s (i) & d p (i) & 0 \end{matrix}]

一直拆到边界，就是：

[\begin{matrix} a n s (l) & d p (l) & 0 \end{matrix}] [\begin{matrix} 0 & - \infty & - \infty \\ a_{l + 1} & a_{l + 1} & - \infty \\ a_{l + 1} & a_{l + 1} & 0 \end{matrix}] \dots [\begin{matrix} 0 & - \infty & - \infty \\ a_{i - 1} & a_{i - 1} & - \infty \\ a_{i - 1} & a_{i - 1} & 0 \end{matrix}] [\begin{matrix} 0 & - \infty & - \infty \\ a_{i} & a_{i} & - \infty \\ a_{i} & a_{i} & 0 \end{matrix}] = [\begin{matrix} a n s (i) & d p (i) & 0 \end{matrix}]

$ans(r)$ $i$ $r$ $ans(l) = dp(l) = a_l$ ，则原式化为：

[\begin{matrix} a_{l} & a_{l} & 0 \end{matrix}] [\begin{matrix} 0 & - \infty & - \infty \\ a_{l + 1} & a_{l + 1} & - \infty \\ a_{l + 1} & a_{l + 1} & 0 \end{matrix}] \dots [\begin{matrix} 0 & - \infty & - \infty \\ a_{r - 1} & a_{r - 1} & - \infty \\ a_{r - 1} & a_{r - 1} & 0 \end{matrix}] [\begin{matrix} 0 & - \infty & - \infty \\ a_{r} & a_{r} & - \infty \\ a_{r} & a_{r} & 0 \end{matrix}] = [\begin{matrix} a n s (r) & d p (r) & 0 \end{matrix}]

$ans(r)$ $\begin{bmatrix} a_l & a_l & 0 \end{bmatrix}$ ，乘上一大堆矩阵。

为了便于书写，我们记：

\begin{matrix} A_{i} = [\begin{matrix} 0 & - \infty & - \infty \\ a_{i} & a_{i} & - \infty \\ a_{i} & a_{i} & 0 \end{matrix}] \end{matrix}

则：

[\begin{matrix} a n s (r) & d p (r) & 0 \end{matrix}] = [\begin{matrix} a_{l} & a_{l} & 0 \end{matrix}] A_{l + 1} A_{l + 2} \dots A_{r - 1} A_{r}

而在实际使用中我们还有很多小技巧与转化来让我们实现起来更简单：

* $3 \times 3$ $3 \times 3$ $3$ $(0, 0)$ $ans(r)$ 即可。

举个例子：

[\begin{matrix} a_{l} & a_{l} & 0 \\ - \infty & - \infty & - \infty \\ - \infty & - \infty & - \infty \end{matrix}]

然后在重载矩阵的乘法的时候，我们应该注意，是否有可能会超出 intlong long $\max$ $-\infty$ $-\infty$ $-\infty$ $-\infty$ 即可。

$l = r$ $\left[ l + 1, r \right]$ $l + 1 \gt r$ ，我们当然可以考虑特判这个情况，但是我们实际上还可以再次转换一下思路，让这个东西更泛用，更美观。

$\begin{bmatrix}a_l & a_l & 0\end{bmatrix}$ $A_l$ 初始矩阵 $T$ $A_l$ $\begin{bmatrix}a_l & a_l & 0\end{bmatrix}$ ，于是很容易写出：

\begin{matrix} T [\begin{matrix} 0 & - \infty & - \infty \\ a_{l} & a_{l} & - \infty \\ a_{l} & a_{l} & 0 \end{matrix}] = [\begin{matrix} a_{l} & a_{l} & 0 \\ - \infty & - \infty & - \infty \\ - \infty & - \infty & - \infty \end{matrix}] \end{matrix}

不难算出：

\begin{matrix} T = [\begin{matrix} - \infty & 0 & 0 \\ - \infty & - \infty & - \infty \\ - \infty & - \infty & - \infty \end{matrix}] \end{matrix}

所以我们的式子就最终变成了：

[\begin{matrix} a n s (r) & d p (r) & 0 \\ - \infty & - \infty & - \infty \\ - \infty & - \infty & - \infty \end{matrix}] = [\begin{matrix} - \infty & 0 & 0 \\ - \infty & - \infty & - \infty \\ - \infty & - \infty & - \infty \end{matrix}] A_{l} A_{l + 1} \dots A_{r - 1} A_{r}

现在这个式子就很好维护了。

$A$ $\left[ l, r \right]$ $A$ $l, r$ ，这不就是区间查询吗，我们于是可以考虑用一些妙妙数据结构去维护这玩意。

$0$ $0$ 是无法确定的，也就是说不一定会存在逆元，所以不能用树状数组或者前缀积之类的东西区间查询。

线段树 $\otimes$ $+$ $\oplus$ $\max$ $O(\xi^3 (n + q))$ $\xi$ $\xi = 3$ 。

$O(1)$ $O(\xi^3(n \log n + q))$ ，具体介绍可以看咕咕日报一种神奇的数据结构——猫树。

当然用平衡树，分块之类的也能做，这里不再过多赘述。

$2^t$ ，且要开好数组范围的大小，否则很容易 RE）

（篇幅原因这里的代码省略了，可以从文章头的链接到原 Blog 访问查看）

例题 #2

题目：[ABC246Ex] 01? Queries。

$N$ 的仅包含 0，1? $S$ $Q$ $(x_1, c_1), (x_2, c_2), \cdots, (x_q, c_q)$ $x_i$ $c_i$ $S$ 有多少种非空子串，? 需任意替换为 0 或 1。

$1 \le N, Q \le 10^5, 1 \le x_i \le N$ 。

我们先不考虑修改，思考对于这样一个字符串能有多少种子串，显然这个东西是个 DP。

$dp(i, 0 / 1)$ $i$ $0$ $1$ 结尾的方案数，显然有如下转移：

$S_i = 1$ ，有：

d p (i, 0) = d p (i - 1, 0)

d p (i, 1) = d p (i - 1, 0) + d p (i - 1, 1) + 1

$S_i = 0$ ，有：

d p (i, 0) = d p (i - 1, 0) + d p (i - 1, 1) + 1

d p (i, 1) = d p (i - 1, 1)

$S_i = \texttt{?}$ ，有：

d p (i, 0) = d p (i - 1, 0) + d p (i - 1, 1) + 1

d p (i, 1) = d p (i - 1, 0) + d p (i - 1, 1) + 1

$\texttt{?}$ 可以认为是任意一个，所以可以接在任意一个的后面。

$+1$ $0$ $0$ $0$ $00$ $0$ $1$ ，于是显然可以保证不重不漏。

这么一大坨分类讨论显然很难维护，那么我们尝试把这些缩到一起：

d p (i, 0) = d p (i - 1, 0) + [S_{i} \neq 1] (d p (i - 1, 1) + 1)

d p (i, 1) = d p (i - 1, 1) + [S_{i} \neq 0] (d p (i - 1, 0) + 1)

$\texttt{true}$ $1$ $0$ 。

现在，我们就可以对这个简洁的式子搞事情了，因为我们后面要有很多次修改，这样的话显然可以考虑 DDP。

我们再次尝试设计出转移的矩阵：

[\begin{matrix} d p (i - 1, 0) & d p (i - 1, 1) \\ 0 & 0 \end{matrix}] T = [\begin{matrix} d p (i, 0) & d p (i, 1) \\ 0 & 0 \end{matrix}]

~~不难算出~~：不难算出我们算不出来。

于是考虑再加一维

[\begin{matrix} d p (i - 1, 0) & d p (i - 1, 1) & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] T = [\begin{matrix} d p (i, 0) & d p (i, 1) & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}]

$T$ ，这东西个人认为实际上就是个蒙猜凑，总之最后弄一下就能出来这个（注意这里我们用的是普通矩乘规则，非广义）：

[\begin{matrix} d p (i - 1, 0) & d p (i - 1, 1) & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] [\begin{matrix} 1 & [S_{i} \neq 0] & 0 \\ [S_{i} \neq 1] & 1 & 0 \\ [S_{i} \neq 1] & [S_{i} \neq 0] & 1 \end{matrix}] = [\begin{matrix} d p (i, 0) & d p (i, 1) & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}]

（不要问我为什么这题用不到广义矩乘还要在前面说一大堆广义矩乘的内容，~~我记错了~~，技多不压身）

然后类比之前的过程，令：

\begin{matrix} A_{i} = [\begin{matrix} 1 & [S_{i} \neq 0] & 0 \\ [S_{i} \neq 1] & 1 & 0 \\ [S_{i} \neq 1] & [S_{i} \neq 0] & 1 \end{matrix}] \end{matrix}

那么一直拆下去，一定有：

[\begin{matrix} d p (1, 0) & d p (1, 1) & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] A_{2} A_{3} \dots A_{n} = [\begin{matrix} d p (n, 0) & d p (n, 1) & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}]

依然尝试找到一个这样的等式：

[\begin{matrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] [\begin{matrix} 1 & [S_{1} \neq 0] & 0 \\ [S_{1} \neq 1] & 1 & 0 \\ [S_{1} \neq 1] & [S_{1} \neq 0] & 1 \end{matrix}] = [\begin{matrix} d p (n, 0) & d p (n, 1) & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}]

所以可以最终化为：

[\begin{matrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] A_{1} A_{2} \dots A_{n} = [\begin{matrix} d p (n, 0) & d p (n, 1) & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}]

$A_i$ 的值，然后查询整个区间。

这玩意有修改显然用不了猫树了，老老实实写线段树吧。。

$O(\xi^3(n + q \log n))$ $\xi = 3$ 。


xxxxxxxxxx
117
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MAXN (int)(1e5 + 100)
24
#define MOD (int)(998244353)
25

26
template< typename T = int >
27
inline T read(void);
28

29
int N, Q;
30
int S[MAXN];
31

32
struct Matrix3{
33
    int val[3][3];
34
    Matrix3(int v00, int v01, int v02, int v10, int v11, int v12, int v20, int v21, int v22):
35
        val{
36
            {v00, v01, v02},
37
            {v10, v11, v12},
38
            {v20, v21, v22}
39
        }{;}
40
    Matrix3(int S):
41
        val{
42
            {1, S != 0, 0},
43
            {S != 1, 1, 0},
44
            {S != 1, S != 0, 1}
45
        }{;}
46
    Matrix3(int val[][3]){for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)this->val[i][j] = val[i][j];}
47
    Matrix3(void) = default;
48
    friend const Matrix3 operator * (const Matrix3 &x, const Matrix3 &y){
49
        int val[3][3]; memset(val, 0, sizeof val);
50
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)for(int p = 0; p <= 2; ++p)
51
            val[i][j] = ((ll)val[i][j] + (ll)x.val[i][p] * y.val[p][j] % MOD) % MOD;
52
        return Matrix3(val);
53
    }
54
    void Print(void){
55
        for(int i = 0; i <= 2; ++i)for(int j = 0; j <= 2; ++j)
56
            printf("%d%c", val[i][j], j == 2 ? '\n' : ' ');
57
    }
58
}mt[MAXN];
59

60
class SegTree{
61
private:
62
    Matrix3 tr[MAXN << 2];
63
    #define LS (p << 1)
64
    #define RS (LS | 1)
65
    #define MID ((gl + gr) >> 1)
66
public:
67
    void Pushup(int p){tr[p] = tr[LS] * tr[RS];}
68
    void Build(int p = 1, int gl = 1, int gr = N){
69
        if(gl == gr)return tr[p] = mt[gl = gr], void();
70
        Build(LS, gl, MID);
71
        Build(RS, MID + 1, gr);
72
        Pushup(p);
73
    }
74
    void Modify(int idx, Matrix3 v, int p = 1, int gl = 1, int gr = N){
75
        if(gl == gr)return tr[p] = v, void();
76
        if(idx <= MID)Modify(idx, v, LS, gl, MID);
77
        else Modify(idx, v, RS, MID + 1, gr);
78
        Pushup(p);
79
    }
80
    Matrix3 Query(void){return tr[1];}
81
}st;
82

83
int main(){
84
    N = read(), Q = read();
85
    string s; cin >> s;
86
    for(int i = 1; i <= (int)s.size(); ++i)
87
        S[i] = s.at(i - 1) == '?' ? -1 : int(s.at(i - 1) - '0'),
88
        mt[i] = Matrix3(S[i]);
89
    st.Build();
90
    Matrix3 origin(0, 0, 1, 0, 0, 0, 0, 0, 0);
91
    while(Q--){
92
        int p = read();
93
        char c = getchar(); while(c != '0' && c != '1' && c != '?')c = getchar();
94
        int flag = c == '?' ? -1 : int(c - '0');
95
        st.Modify(p, Matrix3(flag));
96
        auto ans = origin * st.Query();
97
        printf("%d\n", (int)((ll)(ans.val[0][0] + ans.val[0][1]) % MOD));
98
    }
99
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
100
    return 0;
101
}
102

103
template < typename T >
104
inline T read(void){
105
    T ret(0);
106
    short flag(1);
107
    char c = getchar();
108
    while(c != '-' && !isdigit(c))c = getchar();
109
    if(c == '-')flag = -1, c = getchar();
110
    while(isdigit(c)){
111
        ret *= 10;
112
        ret += int(c - '0');
113
        c = getchar();
114
    }
115
    ret *= flag;
116
    return ret;
117
}

例题 #3

后面对于 DDP 更详尽的讲解可以戳此进入。

UPD

update-2022_10_22 初稿

ABC246Ex 01? Queries Solution

更好的阅读体验戳此进入

浅谈 DDP 与 广义矩阵乘法（戳此进入）

引入

例题 #1

广义矩阵乘法

DDP

例题 #0

例题 #0.5

例题 #1

例题 #2

例题 #3

UPD

浅谈 DDP 与广义矩阵乘法（戳此进入）