CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:李超线段树 [2021/07/13 19:57]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:李超线段树 [2021/07/14 15:51] (当前版本)
jxm2001
@@ 行 410: / 行 410: @@
 [[https://www.luogu.com.cn/problem/P4655|洛谷p4655]]
-=== 题意 ===
+=== 例题一 ===
+**题意**
 给定 $n$ 个点，第 $i$ 个点有两个权值 $h_i,w_i$。要求选定若干个点，记为 $a_1,a_2\cdots a_k$，其中 $1,n$ 号点必选。
@@ 行 416: / 行 418: @@
 费用为 $\sum_{i=1}^{k-1} (a_{i+1}-a_i)^2+\sum_{i \not \in a}w_i$。要求最小化费用。
-=== 题解 ===
+**题解**
 设 $s_i=\sum_{j=1}^i w_i$，$f(i)$ 表示 $n=i$ 的情况下的最小费用，于是有状态转移
@@ 行 489: / 行 491: @@
 </hidden>
+=== 例题二 ===
+[[https://www.luogu.com.cn/problem/P6047|洛谷p6047]]
+**题意**
+给定两条直线，每条直线上依次有 $n$ 个点。然后给定 $m$ 条弦，第 $i$ 条弦的一端位于第一条直线的第 $u_i$ 个点，另一端位于第二条直线的第 $v_i$ 个点。
+每次操作可以选择第一条直线的第 $x$ 个点和第二条直线的第 $y$ 个点，然后割断所有 $u\gt x,v\lt x$ 的弦，同时产生 $a_x\times b_y$ 的费用。
+要求进行若干次操作割断所有的弦同时最小化费用。$(2\le u_i\le n,1\le v_i\le n-1)$
+**题解**
+如果弦 $(u_i,v_i),(u_j,v_j)$ 满足 $u_i\le u_j,v_i\ge v_j$，那割断弦 $i$ 时一定可以割断弦 $j$，于是可以不考虑弦 $j$。
+将剩下的弦 $(u_1,v_1),(u_2,v_2)\cdots (u_k,v_k)$ 按 $u_i$ 从大到小排序，一定满足 $v_i\gt v_{i+1}$。
+设 $sa(i)=\min_{j\le i}(a_j),sb(i)=\min_{j\ge i}(b_j)$，$f(i)$ 表示割断前 $i$ 条弦的最小费用，于是有状态转移
+$$
+f(i)=\min_{0\le j\lt i}\left(f_j+sa(u_i-1)\times sb(v_{j+1}+1)\right)
+$$
+然后套用李超线段树求解即可，时间复杂度 $O(n\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXV=1e6+5,MAXN=3e5+5;
+const LL inf=1LL<<62;
+LL slope[MAXN],b[MAXN];
+int tag[MAXV<<2];
+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(!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(k<<1,lef,mid,tag[k]);
+		else if(slope[v]>slope[tag[k]])
+		update(k<<1|1,mid+1,rig,tag[k]);
+		tag[k]=v;
+	}
+	else{
+		if(slope[v]>slope[tag[k]])
+		update(k<<1,lef,mid,v);
+		else if(slope[v]<slope[tag[k]])
+		update(k<<1|1,mid+1,rig,v);
+	}
+}
+LL query(int k,int lef,int rig,int pos){
+	if(lef==rig)
+	return caly(tag[k],pos);
+	int mid=lef+rig>>1;
+	if(mid>=pos)
+	return min(query(k<<1,lef,mid,pos),caly(tag[k],pos));
+	else
+	return min(query(k<<1|1,mid+1,rig,pos),caly(tag[k],pos));
+}
+struct Node{
+	int u,v;
+	bool operator < (const Node &b)const{
+		return u>b.u||(u==b.u&&v<b.v);
+	}
+}node[MAXN],st[MAXN];
+LL dp[MAXN],wa[MAXN],wb[MAXN];
+int main()
+{
+	int n=read_int(),m=read_int(),maxv=1e6;
+	_rep(i,1,n)wa[i]=read_int();
+	_rep(i,1,n)wb[i]=read_int();
+	_rep(i,2,n)wa[i]=min(wa[i],wa[i-1]);
+	for(int i=n-1;i;i--)wb[i]=min(wb[i],wb[i+1]);
+	_for(i,0,m){
+		node[i].u=read_int();
+		node[i].v=read_int();
+	}
+	sort(node,node+m);
+	int pos=0;
+	_for(i,0,m){
+		while(pos&&st[pos].v<=node[i].v)pos--;
+		st[++pos]=node[i];
+	}
+	_rep(i,1,pos){
+		slope[i]=wb[st[i].v+1],b[i]=dp[i-1];
+		update(1,1,maxv,i);
+		dp[i]=query(1,1,maxv,wa[st[i].u-1]);
+	}
+	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;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具