yzoj P2371 爬山题解

2019 年 10 月 7 日
筆記

背景

其实 Kano 曾经到过由乃⼭，当然这名字⼀看⼭主就是 Yuno 嘛。当年 Kano 看见了由乃⼭，内⼼突然涌出了⼀股杜甫会当凌绝顶，⼀览众⼭⼩的豪⽓，于是毅然决定登⼭。但是 Kano 总是习惯性乱丢垃圾，增重环卫⼯⼈的负担，Yuno 并不想让 Kano 登⼭，于是她果断在⼭上设置了结界……

题意

Yuno 为了⽅便登⼭者，在⼭上造了 N 个营地，编号从 0 开始。当结界发动时，每当第 $ i(> 0) $ 号营地内有⼈，那么他将被传送到第 $ A_i (< i) $ 号营地，如此循环，所以显然最后只会被传送到第 0 号营地。

但 Kano 并不知晓结界的情况。他登⼭的⽅法是这样的：⾸先分⾝出⼀个编号为$ D_i $ 的 Kano，然后将其⽤投⽯机抛掷到营地 $ G_i $ 。Kano 总共做了 M 次这样的登⼭操作，但每次抛出去的 Kano 都被传送回了营地 0，所以 Kano 只好放弃了。

但是 Kano 在思考⼀个问题，到底每个营地被多少只编号不同的 Kano 经过过？

输入

第⼀⾏两个整数 $ N,M，$ 表⽰⼭的营地数和登⼭次数。

接下来 $ N − 1 $ ⾏，每⾏⼀个数，第 $ i $ ⾏为 $ A_i $ ，表⽰营地 i 将会传向营地 $ A_i $ 。

接下来 $ M $ ⾏，每⾏两个数 $ G_i ，D_i $ 。

输出

共 $ N $ ⾏，每⾏表⽰营地 $ i $ 有多少不同编号的 Kano 曾经通过。

数据范围

$ N,M<=10^5, max(D_i) <=10^9 $

看完题考场临时打的暴力，才10分，同机房的大佬暴力90分。。。我菜爆惹

解析

算法一

开一个数组 $ a[i, j] (表示第) i $个点的第 $ j (种标记是否被打过，每次询问可以) O(total) (回答，其中) total $是标记数。

或使用一个计数器，每次有某个 $ a[i, j] $ 从 $ False $ 变 $ True $ 则 $ i $的计数器加1，询问可以做到O(1)。

每次修改暴力打标记。明显的，如果 $ max(D_i) $ 大于 $ M (，则可以通过离散把数量级下降到) M $。

时间复杂度$ O(NM)$，空间复杂度 $ O(Nmax(D_i)) $

算法二

由于每次修改影响到的仅是修改点的祖先，可以换一种储存方式，直接把标记打到点上。每次询问一个点只需要查询该点为根的子树下有多少不同的标记。

这样可以使用DFS序，对每种标记开一个树状数组，对每个标记，查询该子树下是否有标记

时间复杂度 $ O(M log(N)+N max(D_i)log(N)) $，空间复杂度 $ O(N max(D_i)) $

算法三

发现算法二没有必要使用树状数组维护，只需要每种标记分开处理，处理只需要简单地遍历整棵树

时间复杂度 $ O(N max(D_i)) $ , 空间复杂度 $ O(N)$.

算法四

首先我们仅考虑只有一种标记的情况，如果仅有一种标记，那么我们可以把被打标记的点进行+1操作，那么如果最后，一个点的子树和大于 $ 1 $，该点就是有标记的。

但是这样处理不了多种标记的数量，所以要把多余的 $ +1 $ 标记减去，而多余的 $ +1 $ 标记的形成是两个操作拥有公共祖先，所以在两个操作点的 $ LCA $ 处打上一个 $ -1 $ 标记就可避免多加的情况，原来的两个操作也就变成了一个操作了，可以证明-1标记只会打 $ M $ 个。

如此就可以拓展到多种标记，⽽标记数就是该点的⼦树权值和。为了方便打 $ -1 $ 标记，我们可以交换操作顺序，把同⼀种标记的⼀起做,而 $ -1 $ 标记所打的点就是这些相同标记的操作点按 $ DFS $ 序排序之后相邻两点的 $ LCA $ 。
时间复杂度为 $ O(MlogN + N + MlogM) $

ac代码

传送到哪个点便与它建一条边，将其作为父节点，显然 $ 0 $ 为根节点，于是我们只要对分身从小到大进行排序（$ D_i $为第一关键字, $ dfs $ 序为第二关键字），每次枚举 $ D_i $ 相同 $ G_i $ 不同的相邻点对其 $ lca $ 打上 $ -1 $ 标记，其余打上 $ +1 $ 标记，最后跑一遍 $ dfs $ 将每个点的子树的值统计起来就是答案。

#include<bits/stdc++.h>  using namespace std;  const int size=200010;  struct node{      int g;//地点      int d;//编号  }b[size];  int f[size][20],d[size],book[size],st[size],a[size],times;  int ver[2*size],v[size],Next[2*size],head[size];  int m,n,tot,t,ans;  int x,y,z;  queue<int> q;  void add(int x,int y){//建树      ver[++tot]=y;Next[tot]=head[x];head[x]=tot;  }  void dfs(int x){//确定dfs序      v[x]=1;      st[x]=++times;      for(int i=head[x];i;i=Next[i]){          int y=ver[i];          if(v[y]) continue;          dfs(y);      }  }  void bfs(){//lca的预处理      q.push(0);d[0]=1;      while(q.size()){          int x=q.front();q.pop();          for(int i=head[x];i;i=Next[i]){              int y=ver[i];              if(d[y]) continue;              d[y]=d[x]+1;              f[y][0]=x;              for(int j=1;j<=t;++j){                  f[y][j]=f[f[y][j-1]][j-1];              }              q.push(y);          }      }  }  bool cmp(node a,node b){//排序      if(a.d==b.d) return st[a.g]<st[b.g];      else return a.d<b.d;  }  int lca(int x,int y){//lca      if(d[x]>d[y]) swap(x,y);      for(int i=t;i>=0;--i){          if(d[f[y][i]]>=d[x]){              y=f[y][i];          }      }      if(x==y) return x;      for(int i=t;i>=0;--i){          if(f[x][i]!=f[y][i]){              x=f[x][i];              y=f[y][i];          }      }      return f[x][0];  }  void find(int x){//计算答案      v[x]=1;      for(int i=head[x];i;i=Next[i]){          int y=ver[i];          if(v[y]) continue;          find(y);          book[x]+=book[y];      }  }  int main(){      scanf("%d %d",&n,&m);      t=((int)(log(n)/log(2)))+1;      for(int i=1;i<n;++i){//建边          scanf("%d",&a[i]);          add(a[i],i);          add(i,a[i]);      }      for(int i=1;i<=m;++i){          scanf("%d %d",&b[i].g,&b[i].d);      }      dfs(0);      bfs();      sort(b+1,b+1+m,cmp);//按照编号排序，其次按dfs序排序      int pre=-1;//当前点的上一个      for(int i=1;i<=m;++i){//核心代码          int x=b[i].g;          book[x]++;          if(pre!=-1) book[lca(pre,x)]--;//如果编号相同并且地点不同就减去lca          pre=x;          if(i<m&&b[i].d!=b[i+1].d)pre=-1;//判断地点是否相同      }      memset(v,0,sizeof(v));      find(0);      for(int i=0;i<n;++i){          printf("%dn",book[i]);      }      return 0;  }

同机房一位大佬的ac代码（暴力优化跑过！）

#include<cmath>  #include<cstdio>  #include<cstring>  #include<iostream>  #include<algorithm>  using namespace std;    int n,m,arr[100010],ans[100010],sum[100010],tmp;  int pd[100010];  struct dat{      int d,g;  };  dat mov[100010];  bool cmp(dat a,dat b){      if(a.d!=b.d) return a.d<b.d;      return a.g>b.g;  }  int main(){      scanf("%d%d",&n,&m);      --n;      for(int i=1;i<=n;++i) scanf("%d",&arr[i]);      for(int i=1;i<=m;++i) scanf("%d",&mov[i].g),scanf("%d",&mov[i].d);      sort(mov+1,mov+1+m,cmp);      ++m;      for(register int i=1;i<=m;++i){          if(mov[i].d!=mov[i-1].d){              if(mov[i].d!=mov[i+1].d){                  sum[mov[i].g]++;                  continue;              }              ++ans[0];          }          tmp=mov[i].g;          while(tmp){              if(pd[tmp]==mov[i].d) break;              pd[tmp]=mov[i].d;              ++ans[tmp];              tmp=arr[tmp];          }      }      --ans[0];      for(int i=n;i>=1;--i){          sum[arr[i]]+=sum[i];          ans[i]+=sum[i];      }      ans[0]+=sum[0];      for(int i=0;i<=n;++i) printf("%dn",ans[i]);      return 0;  }