题解：CF2057D Gifts Order

SUNCHAOYI

2025-01-07 18:20:18

Solution

这是一篇 DDP 做法的题解。

首先需要想通的一个点就是最值一定出现在端点处，否则区间长度变化而极差不变，会导致答案更劣。

设最值所在的位置为 l,r，则会有两种情况：

若最大值在最小值左侧，则答案为 a_l - a_r - (r - l) = (a_l + l) - (a_r + r)。
若最大值在最小值右侧，则答案为 a_r - a_l - (r - l) = (a_r - r) - (a_l - l)。

不难发现我们只需要维护 a_i + i 和 a_i - i 即可。

当本题不存在修改操作时，就是虹色的北斗七星。设 f_{i,0} 表示 [1,i] 中 a_i + i 的最大值，f_{i,1} 表示 [1,i] 中 a_i - i 的最小值，f_{i,2} 表示 [1,i] 中答案的最大值。于是我们可以得到转移方程：

\begin{cases} f_{i,0} = \max \ \{\ f_{i - 1,0},a_i + i\ \}\\ f_{i,1} = \min \ \{\ f_{i - 1,1},a_i - i\ \}\\ f_{i,2} = \max \ \{\ f_{i - 1,2},f_{i - 1,0} - (a_i + i),(a_i - i) - f_{i - 1,1}\ \} \end{cases}

最后的答案便是 f_{n,2}。进一步可以发现 f_{i,0/1/2} 的值只依赖于前一项，因此我们可以滚动数组优化空间，最后时间复杂度为 O(n)，空间复杂度为 O(1)。为了更好的为 DDP 做准备，可以通过增加负号的方式改写转移方程，使得均变为取 \max 的形式：

\begin{cases} f_{i,0} = \max \ \{\ f_{i - 1,0},a_i + i\ \}\\ f_{i,1} = \color{red}\max\color{black} \ \{\ f_{i - 1,1},\color{red}-\color{black}(a_i - i)\ \}\\ f_{i,2} = \max \ \{\ f_{i - 1,2},f_{i - 1,0} - (a_i + i), (a_i - i)\color{red}{+}\color{black}f_{i - 1,1}\ \} \end{cases}

于是可以得到虹色的北斗七星的核心代码【注意初始化】：

f[0][1] = -INF;
for (int i = 1;i <= n;++i)
{
    int x = read ();
    f[i & 1][0] = max (f[(i + 1) & 1][0],x + i);
    f[i & 1][1] = max (f[(i + 1) & 1][1],-(x - i));
    f[i & 1][2] = max (f[(i + 1) & 1][2],max (f[(i + 1) & 1][0] - (x + i),(x - i) + f[(i + 1) & 1][1]));
}
printf ("%d\n",f[n & 1][2] - 1);

既然已经写成了可以迭代的形式，那么就可以改写成矩阵去维护。当然，这里的矩阵乘法需要被重载为相加取最大值的形式。如下：

\begin{bmatrix} 0 & -\infty & -\infty & a_i + i\\ -\infty & 0 & -\infty & -(a_i - i)\\ -(a_i + i) & a_i - i & 0 & -\infty\\ -\infty & -\infty & -\infty & 0 \end{bmatrix} \begin{bmatrix} f_{i - 1,0}\\ f_{i - 1,1}\\ f_{i - 1,2}\\ 0 \end{bmatrix} = \begin{bmatrix} f_{i,0}\\ f_{i,1}\\ f_{i,2}\\ 0 \end{bmatrix}

由于转移的方程式仍然满足矩阵的结合律，因此用线段树单点修改就可以维护矩阵。但需要注意的是，矩阵不满足交换律，因此需要注意线段树更新时的顺序！令 m = 4，则单组数据的时间复杂度为 O(m^3 q \log n)。

最后放个代码吧：

#include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 2e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
struct Mat
{
    int a[4][4];
    Mat () {init (a);}
    void clear () {init (a);} 
} tree[MAX << 2],I,A;
int t,n,q,a[MAX]; 
Mat operator * (Mat A,Mat B);
void build (int cur,int l,int r);
void modify (int cur,int l,int r,int x,int v);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    I.a[0][1] = I.a[0][2] = I.a[1][0] = I.a[1][2] = I.a[2][3] = I.a[3][0] = I.a[3][1] = I.a[3][2] = -INF;
    t = read ();
    while (t--)
    {
        n = read ();q = read ();
        for (int i = 1;i <= n;++i) a[i] = read ();
        build (1,1,n);
        Mat ans;ans.a[1][0] = -INF;
        ans = tree[1] * ans;
        printf ("%d\n",ans.a[2][0]);
        while (q--)
        {
            int x = read (),v = read ();
            modify (1,1,n,x,v);
            Mat ans;ans.a[1][0] = -INF;//注意初始化 
            ans = tree[1] * ans;
            printf ("%d\n",ans.a[2][0]);
        }
        for (int i = 1;i <= 4 * n;++i) tree[i].clear ();
    }
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
Mat operator * (Mat A,Mat B)
{
    Mat C;
    for (int i = 0;i < 4;++i)
        for (int j = 0;j < 4;++j) C.a[i][j] = -INF;
    for (int i = 0;i < 4;++i)
        for (int j = 0;j < 4;++j)
            for (int k = 0;k < 4;++k) C.a[i][j] = max (C.a[i][j],A.a[i][k] + B.a[k][j]);//重载为相加后取最大值 
    return C;
}
void build (int cur,int l,int r)
{
    if (l == r)
    {
        tree[cur] = I;
        tree[cur].a[0][3] = a[l] + l;tree[cur].a[1][3] = -(a[l] - l);
        tree[cur].a[2][0] = - (a[l] + l);tree[cur].a[2][1] = a[l] - l;  
        return ;
    }
    int mid = (l + r) >> 1;
    build (cur << 1,l,mid);build (cur << 1 | 1,mid + 1,r);
    tree[cur] = tree[cur << 1 | 1] * tree[cur << 1];//注意顺序！！！ 
}
void modify (int cur,int l,int r,int x,int v)
{
    if (l == r)
    {
        a[l] = v;tree[cur] = I;//一些负无穷的处理放在 I 中 
        tree[cur].a[0][3] = a[l] + l;tree[cur].a[1][3] = -(a[l] - l);
        tree[cur].a[2][0] = - (a[l] + l);tree[cur].a[2][1] = a[l] - l;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) modify (cur << 1,l,mid,x,v);
    else modify (cur << 1 | 1,mid + 1,r,x,v);
    tree[cur] = tree[cur << 1 | 1] * tree[cur << 1];//注意顺序！！！ 
}