差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1 [2021/03/27 23:19]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1 [2021/03/29 10:28] (当前版本)
jxm2001 [题解]
@@ 行 204: / 行 204: @@
 	ans=1LL*ans*(((a[i]-b[i])^(1LL*(i+1)*(i+1)))%Mod+1)%Mod;
 	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== F. Squares =====
+==== 题意 ====
+给定一个长度为 $n$ 的序列，每个元素有属性 $p_i,a_i,b_i$，其中 $p_i$ 为 $1\sim n$ 的排列。
+每轮起点为第一个元素，假设当前位于位置 $i$，则可以花费 $a_i$ 到达 $i+1$ 或花费 $b_i$ 到达 $i$ 右边第一个 $p_j\gt j$ 的位置。
+当 $i+1\gt n$ 时花费 $a_i$ 可以到达终点，当 $j$ 不存在时花费 $b_i$ 也可以到达终点。
+给定一个集合 $S$，初始时为空。
+每轮为集合加入或删除一个元素，问在遍历集合中所有元素的前提下到达终点的最小花费。
+==== 题解 ====
+接下来对原图，设每个点连出一条费用为 $a_i$ 的边和费用为 $b_i$ 的边指向对应顶点，同时 $a_0=0,b_0=\infty,p_0=n+1$。
+于是原题转化为求从 $0$ 号结点到终点的最短路径。
+将每个点向左边第一个 $p_j\gt j$ 的元素连一条边，不难发现可以得到一棵树，其中 $0$ 为根节点。
+若当前处于结点 $i$。如果走 $a$ 边则接下来一定会遍历 $i$ 在树上的所有儿子结点，如果走 $b$ 边则将跳过 $i$ 所在的子树的所有结点。
+设最短路中所有 $a$ 边的起点构成的集合为 $T$，此时总费用为
+$$
+\sum_{i\in T}a_i+\sum_{i\not\in T,f(i)\in T}b_i
+$$
+设 $c_i=a_i-b_i+\sum_{j\in \text{child}(i)}b_j,c_0=\sum_{i\in \text{child}(0)}b_i$，则上式化简为 $\sum_{i\in T}c_i$。
+设 $\text{dp}(i)$ 表示 $i\in T$ 时 $T$ 集合中 $i$ 的子树结点的 $c_i$ 和的最小值，则有状态转移方程
+$$
+\text{dp}(i)=c_i+\sum_{j\in \text{child}(i)}\min(\text{dp}(j),0)
+$$
+对每个 $S$ 或 $T$ 中的元素 $u$，该元素的父结点 $p$ 一定属于 $T$，否则不可能进入 $p$ 的子树即不可能到达 $u$。
+于是 $T$ 一定是连通集且 $S$ 的父结点一定属于 $T$，设 $H$ 集合为满足该限制的最小集合，于是最小费用为
+$$
+\begin{equation}\begin{split}
+\sum_{i\in T}c_i&=\sum_{i\in H}\left(c_i+\sum_{j\not\in H,j\in \text{child}(i)}\min(\text{dp}(j),0)\right) \\
+&=\sum_{i\in H}\left(\text{dp}(i)-\sum_{j\in H,j\in \text{child}(i)}\min(\text{dp}(j),0)\right)\\
+&=\text{dp}(0)+\sum_{i\neq 0,i\in H}(\text{dp}(i)-\min(\text{dp}(i),0))\\
+&=\text{dp}(0)+\sum_{i\neq 0,i\in H}\max(\text{dp}(i),0)
+\end{split}\end{equation}
+$$
+接下来考虑如何维护 $H$ 集合即可，将点权转移为到连向父结点的边权，发现可以用类似构建虚树 $\text{dp}$ 的方式维护最小连通集合。
+另外由于本题建树的特殊性，使得可以直接让 $\text{dfs}$ 等于结点编号。时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+typedef set<int>::iterator iter;
+const int MAXN=2e5+5;
+struct Edge{
+	int to,next;
+}edge[MAXN];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int st[MAXN],tp,p[MAXN],a[MAXN],b[MAXN],cnt[MAXN];
+LL c[MAXN],dp[MAXN];
+bool vis[MAXN];
+namespace LCA{
+	int d[MAXN],sz[MAXN],f[MAXN];
+	int h_son[MAXN],mson[MAXN],p[MAXN];
+	LL dis[MAXN];
+	void dfs_1(int u,int fa,int depth){
+		sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+		dp[u]=c[u];
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			dfs_1(v,u,depth+1);
+			dp[u]+=min(dp[v],0LL);
+			sz[u]+=sz[v];
+			if(sz[v]>mson[u])
+			h_son[u]=v,mson[u]=sz[v];
+		}
+	}
+	void dfs_2(int u,int top){
+		p[u]=top;
+		if(mson[u])dfs_2(h_son[u],top);
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==h_son[u])
+			continue;
+			dfs_2(v,v);
+		}
+	}
+	void dfs_3(int u){
+		dis[u]+=max(dp[u],0LL);
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			dis[v]+=dis[u];
+			dfs_3(v);
+		}
+	}
+	void init(int root){
+		dfs_1(root,-1,0);
+		dfs_2(root,root);
+		for(int i=head[root];i;i=edge[i].next)
+		dfs_3(edge[i].to);
+	}
+	int query_lca(int u,int v){
+		while(p[u]!=p[v]){
+			if(d[p[u]]<d[p[v]])swap(u,v);
+			u=f[p[u]];
+		}
+		return d[u]<d[v]?u:v;
+	}
+	LL query_dis(int u,int v){
+		return dis[u]+dis[v]-dis[query_lca(u,v)]*2;
+	}
+};
+int main()
+{
+	int n=read_int(),q=read_int();
+	_rep(i,1,n)p[i]=read_int();
+	_rep(i,1,n)a[i]=read_int();
+	_rep(i,1,n)b[i]=read_int();
+	p[0]=n+1;
+	_rep(i,1,n){
+		while(p[st[tp]]<p[i])tp--;
+		Insert(st[tp],i);
+		st[++tp]=i;
+	}
+	_rep(u,0,n){
+		c[u]=a[u]-b[u];
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			c[u]+=b[v];
+		}
+	}
+	LCA::init(0);
+	set<int> s;
+	s.insert(0);
+	cnt[0]++;
+	LL ans=0;
+	while(q--){
+		int u=read_int(),p=LCA::f[u];
+		if(!vis[u]){
+			cnt[p]++;
+			if(cnt[p]==1){
+				iter rig=s.upper_bound(p);
+				iter lef=--rig;
+				rig++;
+				rig=(rig==s.end())?s.begin():rig;
+				ans+=LCA::query_dis(p,*rig);
+				ans-=LCA::query_dis(*lef,*rig);
+				ans+=LCA::query_dis(*lef,p);
+				s.insert(p);
+			}
+		}
+		else{
+			cnt[p]--;
+			if(cnt[p]==0){
+				iter rig=s.find(p);
+				iter lef=--rig;
+				rig++;rig++;
+				rig=(rig==s.end())?s.begin():rig;
+				ans-=LCA::query_dis(p,*rig);
+				ans+=LCA::query_dis(*lef,*rig);
+				ans-=LCA::query_dis(*lef,p);
+				s.erase(p);
+			}
+		}
+		vis[u]=!vis[u];
+		enter(dp[0]+ans/2);
+	}
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具