首页 > 其他分享 >动态动态规划 & 全局平衡二叉树 小记

动态动态规划 & 全局平衡二叉树 小记

时间:2024-11-01 23:00:09浏览次数:3  
标签:begin end matrix 矩阵 son 二叉树 tf 动态 小记

估计这几天是正式学习 ddp,所以特写笔记。

DDP 简介

是这样一类技巧,利用广义的矩阵乘法实现 单点修改权值,动态查询某个点的 DP 值

关于 矩阵乘法广义矩阵乘法

核心思想是利用矩阵乘法具有结合律(可以使用数据结构维护)的优势

序列上的 Ddp

先看一个例子:最大子段和,显然我们有 \(f_{i}=\max(f_{i-1},0)+a_i\)

现在我们要支持修改点权,还是要求 \(\max f_i\)。

那么我们可以维护这样几个量:\(f_i,g_i=\max_{j\in [1,i]}f_j,a_i\)

也就是有:

\[\begin{cases} f_i=\max(f_{i-1}+a_i,a_i)\\ g_i=\max(g_{i-1},max(f_{i-1}+a_i),a_i)\\ a_i=a_i \end{cases} \]

那么写成 \((\max,+)\) 运算的矩阵形式也就是有:

\[\left[ \begin{matrix} f_{i-1}&g_{i-1}&0 \end{matrix} \right ] \times \left[ \begin{matrix} a_i&0&-\infty\\ -\infty&0&-\infty\\ a_i&-\infty&0 \end{matrix} \right ] = \left[ \begin{matrix} f_{i}&g_{i}&0 \end{matrix} \right ] \]

我们使用线段树维护矩阵乘法,每次单点修改只需要修改这个矩阵,最后求出所有矩阵的积之后就可以求出答案了。

树上的 Ddp

来看一个模板题。

模板:动态 dp & 动态树分治

给定一个带点权的树,求其最大带权独立集权值之和

\(m\) 次询问,每次修改一个点的点权,修改永久生效

容易有如下暴力 dp:

设 \(f_{i,0/1}\) 为当前点是否取的最大权独立集大小(子树内)。

则显然有:

\[\begin{cases} f_{u,0}=\sum_{v\in Son(u)}\max(f_{v,0},f_{v,1})\\ f_{u,1}=w_u+\sum_{v\in Son(u)}f_{v,0}\\ \end{cases} \]

我们能否将其转化为一个序列上的问题呢?

树链剖分,我们可以利用重剖的优秀性质:一条链至多划分为 \(\log n\) 个区间。

那么我们只需要解决:

  1. 维护重链的矩阵运算结果
  2. 维护轻儿子(链顶)向上更新的辅助信息。

考虑将树进行轻重链剖分,同时维护 \(tf\) 表示仅考虑当前点合并轻儿子信息之后的答案,我们定义 \(u\) 的重儿子是 \(son_u\),容易有:

\[\begin{cases} tf_{u,0}&=\sum_{v\in Son(u),v\neq son_u}\max(f_{v,0},f_{v,1})\\ tf_{u,1}&=w_u+\sum_{v\in Son(u),v\neq son_u}f_{v,0}\\ f_{u,0}&=tf_{u,0}+\max(f_{son_u,0},f_{son_u,1})\\ f_{u,1}&=tf_{u,1}+f_{son_u,0} \end{cases} \]

这样做的目的是:保证每个点有唯一前驱,以转化为序列,且容易修改辅助信息的和(至多有 \(\log n\) 次)

首先我们预处理出 \(tf,f\),然后对于每个节点 \(u\) 维护转移矩阵 \(mat_u\),将 \(tf\) 与 \(f_{son}\) 纳入考虑范围,容易有:

\[\left[\begin{matrix} f_{son,0}&f_{son,1} \end{matrix}\right] \times \left[\begin{matrix} tf_{u,0}&tf_{u,1}\\ tf_{u,0}&-\infty \end{matrix}\right] = \left[\begin{matrix} f_{u,0}&f_{u,1} \end{matrix}\right] \]

于是就可以知道 \(mat_u\) 的值了。

这样利用线段树维护区间积就解决了第一个问题。注意转移顺序,是深度大的乘上深度小的转移矩阵,所以线段树上是右区间乘左区间,并且还需要记录链底的编号。

然后我们考虑第二个问题 \(upd(x,k)\),考虑这样解决:

  1. 首先更改 \(mat_x\) 的值

  2. 跳到链顶 \(x\leftarrow top_x\)

    1. 使用 链顶 \(dp\) 值,撤销掉对 \(fa_x\) 的 \(tf\) 影响

    2. 取出新的链顶的 \(dp\) 值

    3. 使用 链顶 \(dp\) 值,加入对 \(fa_x\) 的 \(tf\) 影响

    4. 更新 \(fa_x\) 的转移矩阵

  3. 更新 \(x=fa_x\) 回到 \(2\)

    当当前链顶是树根时候,不需要进行 \(2,3\) 操作

这个题目有一个有趣的性质是叶子节点的转移矩阵第一行可以等效为 \([f_0,f_1]\)。

一般情况下不具备这个性质时需要单独处理

code

复杂度是 \(O(n\log^2 n)\),带八倍矩阵乘法常数。

全局平衡二叉树

这时,你在做完模板题之后发现:你遇到了模板题的加强版:P4751

在数据规模扩大到 \(10^6\) 级别后,似乎树剖有些捉襟见肘,此时我们是否存在更加适合于 Ddp 的结构呢?它就是 全局平衡二叉树

如果您认为在下拙作较为晦涩,欢迎左转 Oi-wiki

算法介绍

我们注意到,树链剖分方法里,有一个地方开销是比较大的,就是利用线段树查询一段区间的矩阵积,考虑优化掉它。

有没有什么办法可以 \(O(1)\) 实现这一步呢?

可以的,我们考虑将每一条重链单独拿出,按照深度建立一颗二叉搜索树(这保证了左右子树加树根是一段连续区间),同时树根维护整个子树的矩阵积,这样的话,我们可以 \(O(1)\) 查询一个子树的矩阵积,就只需要实现如下操作:

  1. 跳到二叉树的父亲(假设存在,同一条重链),pushup
  2. 跳出重链,类似树剖进行撤销和更新,同时继续往上跳。这一步显然是 \(O(\log n)\) 的总共,这一步我们可以对每个二叉树根的父亲设置为链顶在原树上的父亲

发现我们只需要保证跳跃总步数是 \(O(\log n)\) 级别即可。

考虑这样一种剖分策略:定义 \(lsz_u=sz_u-sz_{son_u}\),我们拿出一条重链上的点,做 \(lsz\) 的前缀和,取出它的带权中点(也就是 \(sum\le 2s[1,x]\) 的最小 \(x\)),将它设置为根,剩下两半递归处理。

考虑你从节点 \(u\) 开始向上跳,令一个 \(k\) 为二叉树子树内 \(lsz\) 的和,每跳一个二叉树上的点,这个 \(k\) 会翻倍,与此同时,你跳到另一棵树上时,\(k\) 是不会减少的,综上你每在二叉树上跳一次,那么会使得 \(k\) 翻倍,所以跳二叉树边总次数也是 \(\log n\) 级别的。

因此我们保证了跳跃总步数是 \(\log n\) 级别

3220471-20241023092620127-967361344.png (458×527)

建树后是:

我们称 二叉树边为重边,非二叉树边为轻边

建树是容易的,我们递归每一个重链的链顶,提取出这一条重链,对其递归建树,最后解决父亲的关系即可。

int divide(int l,int r){
    if(l>r)return 0;
    int sum=0;
    for(int i=l;i<=r;++i)sum+=lsz[sta[i]];
    for(int i=l,t=lsz[sta[l]];i<=r;++i,t+=lsz[sta[i]])if(sum<=t*2){
        lc[sta[i]]=divide(l,i-1);
        rc[sta[i]]=divide(i+1,r);
        if(lc[sta[i]])fa[lc[sta[i]]]=sta[i];
        if(rc[sta[i]])fa[rc[sta[i]]]=sta[i];
        pushup(sta[i]);
        return sta[i];
    }
}
int build(int u,int f){
    for(int x=u,l=f;x;l=x,x=son[x])for(auto v:e[x])if(v!=l&&v!=son[x])fa[build(v,x)]=x;
    top=0;for(int x=u;x;x=son[x])sta[++top]=x;
    return divide(1,top);
}

维护 Ddp

我们可以类似于平衡树的方法维护,只不过这个是静态树。

每个点建立两个矩阵 \(mat1,mat2\),其中 \(mat1\) 是自身原本的转移矩阵,而 \(mat2\) 是所在二叉树的子树内 \(mat1\) 合并的结果。

注意合并顺序与矩阵乘法顺序有关系,这一步可以通过 pushup 实现。

void pushup(int x){
    mat2[x]=mat1[x];
    if(lc[x])mat2[x]=mat2[lc[x]]*mat2[x];
    if(rc[x])mat2[x]=mat2[x]*mat2[rc[x]];
}

往上跳的一步,如果没有跳出重链,那么直接 pushup 即可,否则类似树链剖分,撤销并更新 \(tf\)

void upd(int x,int v){
    mat1[x].a[1][0]+=v-w[x];w[x]=v;
    for(int i=x;i;i=fa[i]){
        if(lc[fa[i]]!=i&&rc[fa[i]]!=i&&fa[i]){
            int t=fa[i];
            mat1[t].a[0][0]=mat1[t].a[0][1]=mat1[t].a[0][0]-get2(i);
            mat1[t].a[1][0]-=get(i);
            pushup(i);
            mat1[t].a[0][0]=mat1[t].a[0][1]=mat1[t].a[0][0]+get2(i);
            mat1[t].a[1][0]+=get(i);
        }
        else pushup(i);
    }
}

题目选练

首先模板题已经没了。

保卫王国

比较水的题目啊。

首先考虑这玩意是最小点覆盖,如果用全集减去最大独立集来做的话就是模板题了。不过为了练习我们还是选择打一遍朴素 dp。

首先这个修改可以看作是将点权修改为 \(0\) 或者 \(\infty\),就是动态问题了。

同样考虑设 \(f,tf\),有:

\[\begin{cases} f_{u,0}&=tf_{u,0}+f_{son,1}\\ f_{u,1}&=tf_{u,1}+\min(f_{son,0},f_{son,1})\\ tf_{u,0}&=\sum_{v\in Son(u),v\neq son}f_{v,1}\\ tf_{u,1}&=p_u+\sum_{v\in Son(u),v\neq son}\max(f_{v,0},f_{v,1}) \end{cases} \]

改写为矩阵形式是:

\[\left[\begin{matrix} f_{son,0}&f_{son,1} \end{matrix}\right] \times \left[\begin{matrix} \infty&tf_{u,1}\\ tf_{u,0}&tf_{u,1}\\ \end{matrix}\right] =\left[\begin{matrix} f_{u,0}&f_{u,1} \end{matrix}\right] \]

改改模板就能过了吧。而且这玩意也不需要特判叶子。

code

洪水

这个题的主要目的是说明在全局平衡二叉树上如何查找一个点的 dp 值。

显然我们可以设 \(f_u,tf_u\),显然有转移 \(f_u=\min(w_u,\sum f_v)\)

那么也有:

\[\begin{cases} f_{u}&=\min(w_u,tf_u+f_{son})\\ tf_u&=\sum_{v\in Son(u),v\neq son} f_v\\ \end{cases} \]

由于转移涉及 \(w\),可以设计转移:

\[\left[\begin{matrix} f_{son}&0 \end{matrix}\right] \times \left[\begin{matrix} tf_u&-\infty\\ w_u&0 \end{matrix}\right] = \left[\begin{matrix} f_u&0 \end{matrix}\right] \]

这里可能需要特判叶子。

这里我们考虑全局平衡二叉树如何查找一个节点的 dp 值,整个修改过程是不变的。

譬如我们需要找 \(u\) 的 \(dp\) 值,显然重链上在 \(u\) 后面的那些矩阵其实是 \(u\) 向上跳,当它走左边的时候右边的儿子,一个个组成的,也就是若干的子树操作,这里乘算即可

int gans(int u){
    mat now=mat1[u];if(rc[u])now=mat2[rc[u]]*now;
    while(f[u]&&(lc[f[u]]==u||rc[f[u]]==u)){
        if(lc[f[u]]==u){
            if(rc[f[u]])now=mat2[rc[f[u]]]*mat1[f[u]]*now;
            else now=mat1[f[u]]*now;
        }
        u=f[u];
    }
    return now.a[0][0];
}

code

Min-Max搜索 ZJOI2019

注意题目是 \(\max\),且每个叶子点权不一样。

那么答案的贡献路径是一条链

那么这条链的任何一个点它断掉之后都可以导致答案变化。

由于代价是 \(\max\),我们自然想到枚举 \(k\) 并且求解 \(\le k\) 的问题答案。

这时候我们可以用一个 \(dp\),设 \(f_u\) 为:

  1. 如果 \(u\) 不在答案链上

    \(f_u\) 为其当前值仍然符合答案不变的要求的方案数,例如 \(dep\) 是奇数就是 \(<w_{rt}\),否则是 \(>w_{rt}\)

  2. 如果 \(u\) 在答案链上,\(f_u\) 为当前值不变的方案数。

那么不妨设 \(cnt\) 为叶子节点个数,则显然最终的变化方案数是 \(2^{cnt}-f_1\)。

因为我们保证了所有值不变,它们并未互相影响。

考虑转移

  • 非叶子节点

    显然你可以容斥转移,只要所有儿子非法,那么自己就可以取到一个合法解(例如自身取 \(\min\),这时候所有的儿子是取 \(\max\),它们要求 \(<w_{rt}\),只要它们全部 \(>w_{rt}\) 自身就满足 \(>w_{rt}\) 的要求了)。

    也就是

    \(f_u=\prod_{v\in Son(u)}(2^{c_{v}}-f_v)\),\(c\) 是子树内叶子节点个数

  • 叶子节点

    根据当前节点自身是否可以让其非法且其大小关系是否合适决定是否可以选择这个点让其合法找方案数即可。注意有情况是选了一定会导致非法。这里稍微分讨就好了。

  • 答案链上点

    根据上述非叶子节点的分析

    1. 对于不是答案链上的儿子,乘上 \(2^{c_v}-f_v\)
    2. 对于是答案链上的儿子,乘上 \(f_v\)

这样每次暴力更改可以获得 70 高分。

void dp(int u,int fa,int lim){
    if(lef[u]){
        if(abs(u-wrt)<K&&(lim&1)==(u<wrt))f[u]=1;
        else f[u]=((dep[u]&1)==(u<wrt))<<1;
        return ;
    }
    f[u]=1;
    for(int v:e[u])if(v!=fa){
        dp(v,u,lim);
        f[u]=(pw[sz[v]]+p-f[v])%p*f[u]%p;
    }
}
void dfs(int u,int fa){
    f[u]=1;
    for(auto v:e[u])if(v!=fa){
        if(wrt==val[v])dfs(v,u),f[u]=f[u]*f[v]%p;
        else dp(v,u,dep[u]),f[u]=(pw[sz[v]]+p-f[v])%p*f[u]%p;
    }
}

注意到答案实际上是删掉答案链后,所留下的森林里每棵树的 \(2^{c_v}-f_v\) 的积,并且每次 \(k\) 增大 \(1\) 所改变的点的点权个数是 \(O(1)\) 的,可以考虑对于每个树都使用全局平衡二叉树进行维护。

那么我们就可以设 \(M_u=2^{c_u},tf_u=\prod_{v\in Son(u),v\neq son}(M_v-f_v),C_u=\prod_{v\in Son(u),v\neq son}M_v\)。

就有:

\[\left[ \begin{matrix} M_{son}-f_{son}&M_{son} \end{matrix} \right] \times \left[ \begin{matrix} -tf_u&0\\ C_u&C_u \end{matrix} \right] = \left[ \begin{matrix} M_{u}-f_{u},M_u \end{matrix} \right] \]

注意到乘法可能有零而导致撤销出错,可以维护一个 \(rl_u\) 表示 \(tf_u\) 中去掉所有零之后的数字,同时维护 \(cnt0_{u}\) 表示计算过程中的零的个数来得到真实值。

code

切树游戏 SDOI2017

考虑异或卷积,设 \(F_u(x)\) 为子树 \(u\) 的连通子图(也就是 \(u\) 是深度最小的点)其权值为 \(k\) 的异或生成函数,定义 \(F(x)·G(x)=\sum\sum f_ig_jx^{i\oplus j}\)

注意 \(m\le 128,q\le 30000,change \le 10000\)

感觉有点像 \((n+q)m\log n\) 的味道

考虑暴力DP,可以维护 \(FWT(F_u(x))\),这样有 \(FWT(F_u(x))=FWT(x^{w_u})·\prod_{v\in Son(u)}(FWT(F_v(x))+FWT(0))\)

答案就是 \([x^k]\sum_u IFWT(FWT(F_u(x)))=[x^k]IFWT(\sum FWT(F_u(x)))\)

可以考虑再维护一个 \(FWT(G_u(x))\) 所有子树的 \(FWT(G)\) 加上 \(FWT(u)\)

这样做是 \(nm\log m\) 单次。

这有个弊端就是你每次都必须要把这个 \(IFWT\) 的整个数组弄出来。

直接维护这个向量就好了吧,这个向量对应位置 \(+,*\) 的运算也满足矩阵乘法的要求矩阵乘法的内部元素可以是一个向量

不妨设 \(f_u,g_u\),令 \(·\) 为全一那就有:

\[\begin{cases} f_u=w_u·\prod(f_v+·)\\ g_u=f_u+\sum g_v \end{cases} \]

那么按常理,维护 \(tf_u,tg_u\) 有:

\[\begin{cases} f_u=(f_{son}+·)\times tf_u\\ g_u=(f_{son}+·)\times tf_u+g_{son}+tg_u\\ tf_u=w_u\times \prod_{v\neq son}(f_v+·)\\ tg_u=\sum_{v\neq son} g_v \end{cases} \]

而 \(f,g,tf,tg\) 满足乘法分配律,结合律,加法结合律,交换律,所以我们可以把它当作矩阵来弄。

有:

\[\left [ \begin{matrix} f_{son}&g_{son}&· \end{matrix} \right ] \times \left[\begin{matrix} tf_u&tf_u&0\\ 0&·&0\\ tf_u&tg_u+tf_u&· \end{matrix} \right ]= \left[\begin{matrix} f_u&g_u&· \end{matrix} \right ] \]

注意到在 \(son\) 是叶子时,左侧矩阵与底部行相同,所以可以不用特判

但是修改时怎么撤销呢?预处理所有逆元即可?0 怎么办?。

事实上我们可以像上一个题一样考虑 \(tf\) 的撤销,可以将 \(tf\) 的每一项再维护一下非零值的乘积以及当前零的个数就可以方便的做撤销了,然后再提取值即可。

现在复杂度变成了 \(O(qm\log n)\),带矩阵乘法 27 倍常数,果不其然 TLE。循环展开同样无果。

不必气馁,我们探求一下这个矩阵有什么性质:

\[\left[ \begin{matrix} a&b&0\\ 0&1&0\\ c&d&1 \end{matrix} \right] \times \left[ \begin{matrix} e&f&0\\ 0&1&0\\ g&h&1 \end{matrix} \right] = \left[ \begin{matrix} ae&af+b&0\\ 0&1&0\\ ce+g&cf+d+h&1 \end{matrix} \right] \]

它仍然满足这种形式,可以被 \(a,b,c,d\) 表达,所以我们只需要维护 \(a,b,c,d\) 四个量即可计算矩阵乘法。

这样就降低到了 4 倍常数,可以通过。

标签:begin,end,matrix,矩阵,son,二叉树,tf,动态,小记
From: https://www.cnblogs.com/spdarkle/p/18521437

相关文章

  • WordPress域名更换小记
    WordPress域名更换记录1.准备工作​ 在开始之前,要有一个全面的备份,包括网站的文件和数据库。这确保了如果出现问题,你可以恢复到更改之前的状态。不然中间卡壳直接连后台都打不开了,只能重装。​ 其次,默认你已经有了一个新域名,并且在阿里云域名控制平台做好了解析。2.WordPress......
  • halo配置踩坑过程小记
    写在最前:​ 终于搞定了最后的一步域名解析配置,其实动态博客的折腾程度也不低于当时的hexo吧,也可能当时的痛苦过程已经忘了。。整理一下思路,记录一下配置过程走过的坑。​ 我是从hexo用了半年想折腾点新玩意儿的,其实hexo配置自动化部署之后也挺方便的,反正都是本地编辑写作,后台啥......
  • 动态规划-回文串问题——132.分割回文串II
    1.题目解析题目来源:132.分割回文串II——力扣测试用例2.算法原理首先回文串问题一定首先需要保存每个回文子串出现的位置,即二维dp表来存储所有子字符串中符合回文子串的位置,如图1.状态表示创建一个一维dp表来存储第i个位置之前的字符串数组全部划分为回文子......
  • 【数据结构】二叉树链式结构的实现
    1.前置说明    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成本,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研究......
  • Go语言的动态链接库(DLL)创建和使用
    #Go语言的动态链接库(DLL)创建和使用在讨论Go语言的动态链接库(DLL)创建和使用时,核心要点包括:创建DLL的步骤、调用DLL中的函数、跨平台兼容性问题、性能优化策略。创建DLL的步骤是理解和实践Go语言动态链接库的基础,涉及编写DLL源代码、编译为DLL文件以及确保DLL在目标系统上可用。......
  • (算法)交错字符串————<动态规划>
    1.题⽬链接:97.交错字符串2.题⽬描述:3.解法(动态规划):算法思路:对于两个字符串之间的dp问题,我们⼀般的思考⽅式如下:        i.选取第⼀个字符串的[0,i]区间以及第⼆个字符串的[0,j]区间当成研究对象,结合题⽬的要求来定义「状态表⽰」;        ii.......
  • 代码随想录算法训练营第三十三天|Day33 动态规划
    62.不同路径https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html视频讲解:https://www.bilibili.com/video/BV1ve4y1x7Eu思路int**initDP(intm,intn){int**dp=(int**)malloc(sizeof(int*)*m);inti,j;for(i=0;i<......
  • 中电金信:GienTech动态|丰收之秋,公司多项目获得荣誉
    ​ 中电金信微电影《妙“笔”生花》获国资委表彰  ​ 近日,国务院国资委在京举行中央企业社会主义核心价值观主题微电影(微视频)展映发布活动。中电金信作品《妙“笔”生花》获评第五届中央企业社会主义核心价值观主题微电影(微视频)敬业奉献类优秀作品。该片以中国电子联......
  • (C语言)动态内存管理,柔性数组
    1.为什么存在动态内存分配动态内存管理是C语言提供给我们自主维护空间大小的能力C语言提供了一个动态内存开辟的函数:void*malloc(size_tsize);这个函数向内存申请一块连续可用的空间,并返回指向这块空间的指针。·如果开辟成功,则返回一个指向开辟好空间的指针。·......
  • C#通过反射实现动态属性访问器
    动态属性访问器使用反射,我们可以创建一个动态的属性访问器(DynamicPropertyAccessor),允许我们在运行时访问和修改对象的属性为什么要动态访问为什么不直接访问,而用动态访问?直接访问适用于:编译时就知道要访问的属性追求最高性能的场景简单的属性访问动态访问适用于:运......