The solution of「CF1814E Chain Chips」

· · 题解

\textup{CF1814E Chain Chips}

\textup{Luogu} | \textup{Codeforces} | \textup{Cnblogs} | 动态 dp。

\textup{Description}

在 n 个点的链上，点上分别有不同编号的芯片，两点芯片交换的时候要花费其边权，每次修改边权后询问。

询问要求操作后点编号不等于当前点上芯片的编号，且每个点只有一个芯片，求操作的最小代价。

\textup{Solution}

> 注意到芯片是有来有回的，所以一条路会被经过偶数次。 > > 然后又发现一个芯片互换一定是可以划分为连续段的，考虑将链切成多个小段。 $\textup{Step2}$：这个段有什么性质呢？ > 我们发现，每一个段长不 $\le 3$，证明如下。 > > 三个的时候代价是 $2 a_1 + 2 a_2$，而四个的则为 $2 ( a_1 + a_2 + a_3 ) \ge 2 ( a_1 + a_3 )$，只会更不优。 > > 那么，动态规划的思路是不是稍微清晰一点了吗？ $\textup{Step3}$：朴素 dp 怎么做？ > 定义 $f_i$ 表示前 $i$ 个点满足全部错位的最小代价。 > > 那么最后一段的长度只可能是 $2$ 或 $3$，有： > > $$ > f_{i, j} = \min \begin{cases} f_{i - 2} + 2a_{ i - 1 } \\ > f_{i - 3} + 2a_{i - 2} + 2a_{i - 1} \end{cases} > $$ > > 不难发现，带修所以这是 $O(n \cdot q)$ 的，所以？ $\textup{Step3}$：优化优化。 > 一般这种取 $\min$ 和加法一起做的转移，矩阵是可以做的。 > > 考虑定义矩阵 $g_i$ 使得 $g_i = A \otimes g_{i - 1}$。 > > 因为笔者比较菜，所以特意研究了一下 $\textup{min-plus}(\otimes)$。 > > 其实就是在矩阵乘法的实现上把加法换成取最小值，乘法换成加法，而且有结合律。 > > 正确性应该不难想到。 > > 此时可以让矩阵 $g_i$ 长成类似 $\begin{bmatrix} f_i & f_{i - 1} & f_{i - 2}\end{bmatrix}$ 的样子。 > > 不难得出 $A$ 应该是： > $$ > \begin{bmatrix} f_n \\ f_{n - 1} \\ f_{n - 2} \end{bmatrix} > = \begin{bmatrix} \infty & 2a_{n - 1} & 2a_{n - 1} + 2a_{n - 2} \\ 0 & \infty & \infty \\ \infty & 0 & \infty \end{bmatrix} > \otimes \begin{bmatrix} f_{n - 1} > \\ f_{n - 2} \\ f_{n - 3} \end{bmatrix} $$ > > 那么如何维护这种动态修改的矩阵呢？ $\textup{Step4}$：说到修改，我记得一个数据结构。 > 修改 $a_i$ 的时候，只会涉及到 $A_{i + 1},A_{i + 2}$。 > > 那我们只需要在线段树中维护这个矩阵更新就可以了。 > > 感觉讲的有点抽象，我讲一下实现应该能明白。 > > 线段树叶子节点存转移矩阵 $A$，并且存左右儿子矩阵的乘积，细节注意线段树没有交换律，所以是先右再左。 > > 最后是实现的时候记得特判 $N=2$ 的情况，原因在[这里](https://www.luogu.com.cn/discuss/1324963)。 > > 可以写代码了。 --- ## $\textup{Code}

\textup{Rec.}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int N, Q;
int a[MAXN];
struct matrix{
    int a[4][4];

    void init(){
        for( int i = 0; i < 4; i ++ )
            for( int j = 0; j < 4; j ++ )
                a[i][j] = inf;
    }

    matrix operator * ( const matrix & b ){
        matrix res;
        res.init();
        for( int i = 1; i < 4; i ++ ){
            for( int j = 1; j < 4; j ++ ){
                for( int k = 1; k < 4; k ++ ){
                    if( a[i][k] == inf || b.a[k][j] == inf ) continue;
                    res.a[i][j] = min( res.a[i][j], a[i][k] + b.a[k][j] );
                }
            }
        }
        return res;
    }
}tr[MAXN << 2];

matrix gett( int i ){
    matrix now;
    now.init();
    now.a[1][2] = 2 * a[i - 1], now.a[1][3] = 2 * a[i - 1] + 2 * a[i - 2];
    now.a[2][1] = now.a[3][2] = 0;
    return now;
}

void build( int p, int l, int r ){
    if( l == r ){
        tr[p] = gett( l );
        return;
    }
    int mid = ( l + r ) >> 1;
    build( p << 1, l, mid ), build( p << 1 | 1, mid + 1, r );
    tr[p] = tr[p << 1 | 1] * tr[p << 1];
}

void mdf( int p, int l, int r, int x ){
    if( l == r ){
        tr[p] = gett( l );
        return;
    }
    int mid = ( l + r ) >> 1;
    if( x <= mid ) mdf( p << 1, l, mid, x );
    else mdf( p << 1 | 1, mid + 1, r, x );
    tr[p] = tr[p << 1 | 1] * tr[p << 1];
}
signed main(){
    cin >> N;
    for( int i = 1; i < N; i ++ ){
        cin >> a[i];
    }
    if( N == 2 ){
        cin >> Q;
        while( Q -- ){
            int k, x;
            cin >> k >> x;
            a[k] = x;
            cout << 2 * a[1] << "\n";
        }
        return 0;
    }
    build( 1, 3, N );
    cin >> Q;
    while( Q -- ){
        int k, x;
        cin >> k >> x;
        a[k] = x;
        if( k + 1 >= 3 && k + 1 <= N ) mdf( 1, 3, N, k + 1 );
        if( k + 2 >= 3 && k + 2 <= N ) mdf( 1, 3, N, k + 2 );
        int g[4] = { 0, 2 * a[1], inf, 0 }, ans = inf;
        for( int i = 1; i <= 3; i ++ ){
            if( tr[1].a[1][i] != inf && g[i] != inf ){
                ans = min( ans, tr[1].a[1][i] + g[i] );
            }
        }
        cout << ans << endl;
    }
    return 0;
}

\textup{Last}

审核管理员辛苦了，如果您有所疑惑或我有所错漏，请您在评论区指出或找我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗？

谢谢你看到这里~