GSS1 - Can you answer these queries I

· · 题解

简要题意

给你一个长度为 n 的序列 a，q 次询问，每次询问给出一个区间 [l,r]，求区间的最大子段和。

1\leq n,q\leq 5\times10^4

思路

翻了翻题解区没有动态 dp 的做法，所以在此给一个动态 dp 的做法供参考，这也是我做的第一道动态 dp 题。

首先考虑一个朴素的问题：

给出一个序列 a，求出它的最大子段和。

对于这个问题，我们可以朴素的 dp，设 f_i 表示以 i 结尾的最大子段和，g_i 表示 f_i 的前缀最大值，则答案就是 g_i。

转移是容易的：f_i=\max(f_{i-1}+a_i,a_i),g_i=\max(f_i,g_{i-1})。

然后我们考虑构造转移矩阵，大概长这样：

F_i=\begin{bmatrix} F_{11}&F_{12}&F_{13}\\ F_{21}&F_{22}&F_{23}\\ F_{31}&F_{32}&F_{33} \end{bmatrix}

需要满足

F_i\times\begin{bmatrix} f_{i-1}\\ g_{i-1}\\ 0 \end{bmatrix}=\begin{bmatrix} f_{i}\\ g_{i}\\ 0 \end{bmatrix}

注意这里的乘法是指 (\max,+) 的广义矩阵乘法。

然后我们考虑构造，首先构造第一行：

然后考虑第二行，发现 g_i 是一个前缀最大值的形式不便和 f 一起转移。将 g_i 中的 f_i 拆掉，得 \max(f_{i-1}+a_i,a_i,g_{i-1})：

最后考虑第三行，只需要令 F_{33}=0 即可。

其余的位置不参与转移，填 -\infty 即可。

所以得到：

F_i=\begin{bmatrix} a_i&-\infty&a_i\\ a_i&0&a_i\\ -\infty&-\infty&0 \end{bmatrix}

我们考虑如何递推，考察 F_i 定义式发现后面是一个尾递归（这个词可能不太严谨，理解即可）的形式，边界在 F_l，所以答案就是：

\left(\prod_{k=l+1}^{r}F_k\right)\begin{bmatrix} a_l\\0 \end{bmatrix}

由于广义矩阵乘法具有结合律，所以我们可以用线段树来维护上面那个求积式。

时间复杂度 O(n+q\log n)。

代码

#include <bits/stdc++.h>
#define int long long
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;

const int N = 1e5+5;
int n,q,a[N];

struct matrix{
    int n,m,a[4][4];
    int* operator[](int x){return this->a[x];}
    explicit matrix(int N = 0, int M = 0) : n(N), m(M) {};
    void clear(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) a[i][j] = INT_MIN;
        }
    }
    void output(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) cout<<a[i][j]<<' ';
            cout<<'\n';
        }
    }
};

matrix bdmtx(int i){
    matrix ans(3, 3);
    ans[1][1] = ans[1][3] = ans[2][1] = ans[2][3] = a[i];
    ans[1][2] = ans[3][1] = ans[3][2] = INT_MIN;
    ans[2][2] = ans[3][3] = 0;
    return ans;
}

matrix operator*(matrix a,matrix b){
    matrix c(a.n, b.m);
    assert(a.m == b.n);
    c.clear();
    for(int k=1;k<=a.m;k++){
        for(int i=1;i<=a.n;i++){
            for(int j=1;j<=b.m;j++) c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
        }
    }
    return c;
}

matrix t[N<<2];

void build(int i, int l, int r){
    if(l == r){
        cin>>a[l];
        t[i] = bdmtx(l);
        return; 
    }
    build(ls, l, mid);build(rs, mid + 1, r);
    t[i] = t[rs] * t[ls];
}

matrix query(int ql, int qr, int i, int l, int r){
    if(ql <= l && r <= qr){
        // cout<<"Range: "<<l<<' '<<r<<'\n';
        // t[i].output();
        return t[i];
    }
    if(ql <= mid && !(qr > mid)) return query(ql, qr, ls, l, mid);
    if(qr > mid && !(ql <= mid)) return query(ql, qr, rs, mid + 1, r);
    return query(ql, qr, rs, mid + 1, r) * query(ql, qr, ls, l, mid);
}

int bf(int l, int r){
    if(l == r) return a[l];
    matrix ans(3, 1);
    ans.clear();
    ans[1][1] = ans[2][1] = a[l], ans[3][1] = 0;
    for(int i=l+1;i<=r;i++) ans = bdmtx(i) * ans;
    return (ans)[2][1];
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    build(1, 1, n);
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        if(l == r){
            cout<<a[l]<<'\n';
            continue;
        }
        matrix ans;
        ans.n = 3, ans.m = 1;
        ans[1][1] = ans[2][1] = a[l], ans[3][1] = 0;
        ans = query(l + 1, r, 1, 1, n) * ans;
        cout<<ans[2][1]<<'\n';
    }
    return 0;
}