动态 DP - OIer某罗 -

例题1：最大子段和问题，区间询问版本。

https://www.luogu.com.cn/problem/SP1043

\(1 \le n, q \le 4 \times 10^5\)

考虑 dp。首先考虑简单版本：令 \(dp_i\) 表示以第 \(i\) 个元素为结尾的最大子段和。

根据矩阵乘法的重新定义，我们可以把它写成矩阵，其中“乘”->“加”，“加”->“\(\max\)”。也就是：

考虑求

有

也就是我们对于每次询问需要求出 $ \mathbf{A_R}\mathbf{A_{R-1}}...\mathbf{A_{L+1}}$。

注意到 \(\mathbf{A_i}\) 和 \(a_i\) 有关，且只和 \(a_i\) 有关。怎么求？考虑我们做序列连续和怎么做。前缀和/差分；树状数组；线段树...

考虑前缀积，但是由于矩阵不一定存在逆（需要高斯消元方程有解），不行。

考虑树状数组，我们复习一下树状数组的性质，发现差分需要有逆操作，但是矩阵不一定存在逆，不行。

于是我们可以用线段树。每一个节点维护一个矩阵，上传操作是矩阵乘法。不需要修改，只需要查询区间积即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e12;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
struct mat {
    int a[5][5];
    mat() {
        memset(a, 0xcf, sizeof(a));
    }

    mat operator* (mat b) {
        mat c = mat();
        f(i, 1, 2) {
            f(k, 1, 2) {
                int r = a[i][k];
                f(j, 1, 2) {
                    c.a[i][j] = max(c.a[i][j], r + b.a[k][j]);
                }
            }
        }
        return c;
    }
    mat operator^ (int b) {
        mat c = mat(), x = *this;
        f(i, 1, 2) c.a[i][i] = 0;
        while(b){
            if(b&1)c=c*(*this);
            (*this)=(*this)*(*this);
            b>>=1;
        }
        return c;
    }
};
struct sgt {
    mat A = mat();
}t[300010];
int y[300010];
void build(int now, int l, int r) {
    if(l == r) {
        t[now].A.a[1][1] = t[now].A.a[1][2] = y[l];
        t[now].A.a[2][1] = -inf; t[now].A.a[2][2] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(now * 2, l, mid);
    build(now * 2 + 1, mid + 1, r);
    t[now].A = t[now * 2].A * t[now * 2 + 1].A; 
}
mat query(int now, int l, int r, int x, int y) {
    if(l >= x && r <= y) {
        return t[now].A;
    }
    if(l > y || r < x) {
        mat ret = mat();
        f(i, 1, 2) ret.a[i][i] = 0;
        return ret;
    }
    int mid = (l + r) >> 1;
    return query(now * 2, l, mid, x, y) * query(now * 2 +1, mid + 1, r, x, y);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int n; cin >> n;
    f(i, 1, n) cin >> y[i];
    build(1, 1, n);
    int m; cin >> m;
    f(i,1,m){
        int l,r;cin>>l>>r;
        mat tar = mat();
        tar.a[1][1] = y[l], tar.a[2][1] = 0;
        mat rat = query(1, 1, n, l + 1, r);
        rat = rat * tar;
        cout << rat.a[1][1] << endl;
    }
    time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
} 

现在考虑原问题怎么做。【待补充】

例题2：带单点修改。

\(q\) 次修改单点 \(a_i\) + 询问。

\(1 \le n, q \le 2 \times 10^5\)

每次在线段树中单点修改 \(A_i\) 即可。