用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
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;​  ans=1LL*ans*(((a[i]-b[i])^(1LL*(i+1)*(i+1)))%Mod+1)%Mod;​
  enter(ans);​  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;  return 0;
 } }
 </​code>​ </​code>​
 </​hidden>​ </​hidden>​
2020-2021/teams/legal_string/jxm2001/contest/cf_706_div._1.1616858341.txt.gz · 最后更改: 2021/03/27 23:19 由 jxm2001