[CF1814E] Chain Chips 题解

· · 题解

由于操作完必须形成一个排列，于是每条边必须被操作偶数次，否则这条边左右不能平衡。

进一步发现，每条边最多操作 2 次，考虑一个由操作数不为 0 的边构成的连通块，只需要从左往右依次给每条边操作 2 次就可以将连通块内所有点错位。

于是一条边只有选和不选两种情况，要求不能有连续两条边不选，代价为选的边的边权之和 \times 2。这是一个经典的最大权独立集问题，使用 dp 解决。设 f_{i,0/1} 表示考虑到第 i 条边，这条边选/不选的最大代价，转移有三条：f_{i,0}+a_i\to f_{i,1},f_{i,1}\to f_{i,0},f_{i,1}+a_i\to f_{i,1}。

考虑修改，显然转移形如 (\min,+) 矩乘，具体为 \begin{bmatrix}f_{i,0}&f_{i,1}\end{bmatrix}\times\begin{bmatrix}\infty&a_i\\0&a_i\end{bmatrix}=\begin{bmatrix}f_{i+1,0}&f_{i+1,1}\end{bmatrix}，每条边是一个转移矩阵，答案为所有矩阵从左到右乘起来，修改时只需要修改一个矩阵，于是直接线段树维护即可。

时间复杂度 \mathcal{O}(d^3n\log n)，其中 d=2。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=200007,ee=1e18;
ll n,q,a[maxn];
void ups(ll &a,ll b){a=min(a,b);}
struct Matrix{
    ll a[2][2];
    Matrix(void){memset(a,0x3f,sizeof(a));}
    void fill(ll x){a[0][1]=a[1][1]=x,a[1][0]=0;}
    Matrix operator*(Matrix &o){
        Matrix res;
        for(ll i=0;i<=1;i++)for(ll j=0;j<=1;j++){
            for(ll k=0;k<=1;k++) ups(res.a[i][j],a[i][k]+o.a[k][j]);
        }
        return res;
    }
    void op(void){
        cout<<a[0][0]<<" "<<a[0][1]<<"\n";
        cout<<a[1][0]<<" "<<a[1][1]<<"\n\n";
    }
};
struct Tree{
    Matrix val[maxn<<2];
    void build(ll l,ll r,ll rt){
        if(l==r){
            val[rt].fill(a[l]); 
            if(l==n-1||l==1) val[rt].a[1][0]=ee;
            return;
        }
        ll mid=(l+r)>>1;
        build(l,mid,rt<<1),build(mid+1,r,rt<<1|1);
        val[rt]=val[rt<<1]*val[rt<<1|1];
    }
    void modify(ll l,ll r,ll x,ll z,ll rt){
        if(l==r){
            val[rt].fill(z);
            if(l==n-1||l==1) val[rt].a[1][0]=ee;
            return;
        }
        ll mid=(l+r)>>1;
        if(x<=mid) modify(l,mid,x,z,rt<<1);
        else modify(mid+1,r,x,z,rt<<1|1);
        val[rt]=val[rt<<1]*val[rt<<1|1];
    }
}tree;
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(ll i=1;i<n;i++) cin>>a[i];
    tree.build(1,n-1,1);
    cin>>q;
    for(ll i=1,x,y;i<=q;i++){
        cin>>x>>y;
        tree.modify(1,n-1,x,y,1);
        Matrix res=tree.val[1];
        cout<<res.a[0][1]*2<<"\n";
    }
    return 0;
}

::::