2020-2021:teams:legal_string:jxm2001:李超线段树
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:李超线段树 [2021/07/14 10:12] jxm2001 [斜率优化 $\text{DP}$] |
2020-2021:teams:legal_string:jxm2001:李超线段树 [2021/07/14 15:51] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 515: | 行 515: | ||
| $$ | $$ | ||
| - | 然后套用李超线段树求解即可，时间复杂度 $O(n\log V)$。 | + | 然后套用李超线段树求解即可，时间复杂度 $O(n\log v)$。 |
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 590: | 行 590: | ||
| } | } | ||
| enter(dp[pos]); | enter(dp[pos]); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 李超线段树合并 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/CF932F|CF932F]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定一棵以 $1$ 为根的有根树，树上每个点有两种点权 $a_i,b_i$。 | ||
| + | |||
| + | 人物可以从所在节点 $u$ 移动到子树中的任意节点 $v$，费用为 $a_u\times b_v$。问人物从每个节点出发到达任意叶子节点的最小费用。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 设 $\text{dp}(u)$ 表示人物从点 $u$ 出发移动到任意叶子节点的最小费用，显然有状态转移 | ||
| + | |||
| + | $$ | ||
| + | \text{dp}(u)=\min\left(\text{dp}(v)+a_u\times b_v\right) | ||
| + | $$ | ||
| + | |||
| + | 每个节点维护子树的李超线段树，然后进行线段树合并即可。 | ||
| + | |||
| + | 关于李超线段树的合并时间复杂度，普通线段树合并复杂度为 $O(n\log v)$，但是李超线段树合并单个节点时进行了更新操作，需要单独考虑。 | ||
| + | |||
| + | 首先不难发现每条直线只会作为李超线段中至多一个节点的最优解存在。 | ||
| + | |||
| + | 而李超线段树的更新操作在每次递归时要么永远删除一条直线，要么将一条直线下放，使这条直线在李超线段树的深度 $+1$。 | ||
| + | |||
| + | 而一共只有 $O(n)$ 条直线，于是深度和最大为 $O(n\log v)$，根据势能分析法，得更新操作的总时间复杂为 $O(n\log v)$。 | ||
| + | |||
| + | 于是李超线段树合并的总复杂度为 $O(n\log v)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXV=2e5+5,MAXN=1e5+5,N=1e5; | ||
| + | const LL inf=1LL<<62; | ||
| + | LL slope[MAXN],b[MAXN]; | ||
| + | int tag[MAXV*30],ch[MAXV*30][2],node_cnt; | ||
| + | LL caly(int v,LL x){ | ||
| + | return v==0?inf:slope[v]*x+b[v]; | ||
| + | } | ||
| + | void update(int &k,int lef,int rig,int v){ | ||
| + | if(!k)k=++node_cnt; | ||
| + | if(!tag[k]){ | ||
| + | tag[k]=v; | ||
| + | return; | ||
| + | } | ||
| + | int mid=lef+rig>>1; | ||
| + | LL y1=caly(v,mid),y2=caly(tag[k],mid); | ||
| + | if(lef==rig){ | ||
| + | tag[k]=y1<y2?v:tag[k]; | ||
| + | return; | ||
| + | } | ||
| + | if(y1<y2){ | ||
| + | if(slope[v]<slope[tag[k]]) | ||
| + | update(ch[k][0],lef,mid,tag[k]); | ||
| + | else if(slope[v]>slope[tag[k]]) | ||
| + | update(ch[k][1],mid+1,rig,tag[k]); | ||
| + | tag[k]=v; | ||
| + | } | ||
| + | else{ | ||
| + | if(slope[v]>slope[tag[k]]) | ||
| + | update(ch[k][0],lef,mid,v); | ||
| + | else if(slope[v]<slope[tag[k]]) | ||
| + | update(ch[k][1],mid+1,rig,v); | ||
| + | } | ||
| + | } | ||
| + | void Merge(int &k1,int k2,int lef,int rig){ | ||
| + | if(!k1||!k2){ | ||
| + | k1|=k2; | ||
| + | return; | ||
| + | } | ||
| + | int mid=lef+rig>>1; | ||
| + | if(lef==rig){ | ||
| + | tag[k1]=caly(tag[k1],mid)<caly(tag[k2],mid)?tag[k1]:tag[k2]; | ||
| + | return; | ||
| + | } | ||
| + | Merge(ch[k1][0],ch[k2][0],lef,mid); | ||
| + | Merge(ch[k1][1],ch[k2][1],mid+1,rig); | ||
| + | update(k1,lef,rig,tag[k2]); | ||
| + | } | ||
| + | LL query(int k,int lef,int rig,int pos){ | ||
| + | if(!k)return inf; | ||
| + | if(lef==rig)return caly(tag[k],pos); | ||
| + | int mid=lef+rig>>1; | ||
| + | if(mid>=pos) | ||
| + | return min(query(ch[k][0],lef,mid,pos),caly(tag[k],pos)); | ||
| + | else | ||
| + | return min(query(ch[k][1],mid+1,rig,pos),caly(tag[k],pos)); | ||
| + | } | ||
| + | LL dp[MAXN],wa[MAXN],wb[MAXN]; | ||
| + | int rt[MAXN]; | ||
| + | struct Edge{ | ||
| + | int to,next; | ||
| + | }edge[MAXN<<1]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v){ | ||
| + | edge[++edge_cnt]=Edge{v,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | void dfs(int u,int fa){ | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(v==fa)continue; | ||
| + | dfs(v,u); | ||
| + | Merge(rt[u],rt[v],-N,N); | ||
| + | } | ||
| + | if(rt[u]) | ||
| + | dp[u]=query(rt[u],-N,N,wa[u]); | ||
| + | else | ||
| + | dp[u]=0; | ||
| + | slope[u]=wb[u],b[u]=dp[u]; | ||
| + | update(rt[u],-N,N,u); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(); | ||
| + | _rep(i,1,n)wa[i]=read_int(); | ||
| + | _rep(i,1,n)wb[i]=read_int(); | ||
| + | _for(i,1,n){ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | Insert(u,v); | ||
| + | Insert(v,u); | ||
| + | } | ||
| + | dfs(1,0); | ||
| + | _rep(i,1,n) | ||
| + | space(dp[i]); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/李超线段树.1626228731.txt.gz · 最后更改: 2021/07/14 10:12 由 jxm2001
