[DS记录]P5528 [Ynoi2012]WC,THUWC,CTSC与APIO2017

· · 个人记录

题意 ： 维护一颗有根树，点有点权，边权均为 1 ，支持下列操作 ：

------------ 和 `P5309` 有点类似，但难度超出许多。 取阈值 $B$。 - $x\leq B

对于每个 x 分别计算。

将点按照深度 \bmod\ x 的值分组，显然，一次修改只会涉及 (dep[u]+y)\bmod x 组中的点。

对每个组按照 \rm dfs 序排序，子树的约束相当于一个区间。

可以一开始就把点按照 \rm dfs 序排序，然后使用桶分类，这样组中自然有序。

查找需要修改的区间时需要 lower_bound，可以进一步离线变为线性，不过由于这部分常数不算大，没必要。

注意到修改有 O(n) 个，贡献到询问的次数共 O(n\sqrt{n})，使用 O(\sqrt{n}) 修改 O(1) 查询的分块即可。

由于没有强制在线，对每个 x 逐次处理可以做到 O(n) 空间。

一个点的所有 k 级后代在 \rm BFS 序上排列为一个连续段。

可以将问题转化为 O(\sqrt{n}) 次区间加法，使用 O(1) 修改 O(\sqrt{n}) 查询的分块即可。

问题在于如何找到修改的左右端点。

可以模仿前面的做法，在对应深度的一层二分，但是需要多个 \log。

定义一个点的 lson 为 ： 所有兄弟的 bfs 序最小的儿子。

这样，跳 k 次 lson 后，若还在自己子树内，就能得到最左侧的点，右侧点类似。不难发现这就是 k 级祖先问题。

可以使用长链剖分做到 O(n\log n) 预处理，O(1) 询问。但这做法常数较大且实现略为繁琐。

然而，我们的查询是有性质的 : 查询一个点的 y,x+y,2x+y... 级祖先。

可以使用重链剖分，跳过的重链一共是 O(\log n) 条的，由此导致的额外复杂度可不计。

综上，令 B=\sqrt{n/\log n} ，时间复杂度 O(n\sqrt{n\log n}) ，空间复杂度 O(n)。

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define pb push_back
#define MaxN 300500
using namespace std;
int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
int BS,n;
struct SumDS1
{
  int o[MaxN],s[605];
  void clear(){
    memset(o,0,sizeof(int)*(n+5));
    memset(s,0,sizeof(s));
  }
  inline void add(int p,int c)
  {o[p]+=c;s[p/BS]+=c;}
  int qry(int p){
    int bp=p/BS,ret=0;
    for (int i=0;i<bp;i++)ret+=s[i];
    for (int i=bp*BS;i<=p;i++)ret+=o[i];
    return ret;
  }
}T1;
struct SumDS2
{
  int o[MaxN],s[605];
  void clear(){
    memset(o,0,sizeof(int)*(n+5));
    memset(s,0,sizeof(s));
  }
  void add(int p,int c){
    int bl=p/BS;
    for (int i=p;i<(bl+1)*BS;i++)o[i]+=c;
    for (int i=bl;i*BS<=n;i++)s[i]+=c;
  }
  inline int qry(int p)
  {return s[p/BS-1]+o[p];}
}T2;
struct FtpDS{
  vector<int> g[MaxN];
  int f[MaxN],tf[MaxN],siz[MaxN],mp[MaxN]
     ,tp[MaxN],dfn[MaxN],tim;
  void pfs1(int u)
  {
    siz[u]=1;
    for (int i=0,v;i<g[u].size();i++){
      pfs1(v=g[u][i]);
      siz[u]+=siz[v];
      if (siz[mp[u]]<siz[v])
        mp[u]=v;
    }
  }
  void pfs2(int u,int top)
  {
    tp[dfn[u]=++tim]=u;
    tf[u]=top;
    if (mp[u])pfs2(mp[u],top);
    for (int i=0,v;i<g[u].size();i++)
      if ((v=g[u][i])!=mp[u])
        pfs2(v,v);
  }
  void Init(){
    for (int i=1;i<=n;i++)
      if (f[i])g[f[i]].pb(i);
    for (int i=1;i<=n;i++)
      if (!f[i]){pfs1(i);pfs2(i,i);}
  }
  int find(int u,int k){
    while (u&&dfn[u]-dfn[tf[u]]<k){ 
      k-=dfn[u]-dfn[tf[u]]+1;
      u=f[tf[u]];
    } return u ? tp[dfn[u]-k] : 0;
  }
}FL,FR;
vector<int> g[MaxN];
int dfn[MaxN],out[MaxN],tim
   ,dep[MaxN],tp[MaxN];
void pfs(int u) 
{
  tp[dfn[u]=++tim]=u;
  for (int i=0;i<g[u].size();i++){
    dep[g[u][i]]=dep[u]+1;
    pfs(g[u][i]);
  }out[u]=g[u].empty() ? u : out[g[u].back()];
}
void bfs(int *q,int *tl,int *tr)
{
  int l=1,r=1;q[l]=1;
  while(l<=r){
    int u=q[l];l++;
    for (int i=0;i<g[u].size();i++)
      q[++r]=g[u][i];
  }
  for (int u=1;u<=n;u++)
    if (!g[u].empty()){
      tl[u]=g[u].front();
      tr[u]=g[u].back();
    }
  for (int i=n;i;i--)
    if (!tl[q[i]]&&dep[q[i]]==dep[q[i+1]])
      tl[q[i]]=tl[q[i+1]];
  for (int i=1;i<=n;i++)
    if (!tr[q[i]]&&dep[q[i]]==dep[q[i-1]])
      tr[q[i]]=tr[q[i-1]];
}
int p[MaxN],id[MaxN];
void mdf(int u,int x,int y,int c)
{
  int l=FL.find(u,y),r=FR.find(u,y);
  while(dfn[u]<=dfn[l]&&dfn[l]<=dfn[out[u]]){
    T1.add(id[l],c);T1.add(id[r]+1,-c);
    l=FL.find(l,x);r=FR.find(r,x);
  }
}
struct Data{int op,u,x,y,c;}b[MaxN];
int m,V,dx[MaxN],ans[MaxN];
bool cmp(int A,int B){return dfn[A]<dfn[B];}
int main()
{
  n=read();m=read();
  BS=sqrt(n)+2;
  V=sqrt(n/log(n))+2;
  for (int i=2;i<=n;i++)
    g[read()].pb(i);
  pfs(1);
  bfs(p,FL.f,FR.f);
  FL.Init();FR.Init();
  for (int i=1;i<=n;i++)id[p[i]]=i;
  for (int i=1,op;i<=m;i++){
    b[i].op=read();b[i].u=read();
    if (b[i].op==1){
      b[i].x=read();
      b[i].y=read();
      b[i].c=read();
      if (b[i].x>V)
        mdf(b[i].u,b[i].x,b[i].y,b[i].c);
      else b[i].y=(b[i].y+dep[b[i].u])%b[i].x;
    }else ans[i]=T1.qry(id[b[i].u]);
  }
  for (int x=1;x<=V;x++){
    static int o[605];
    for (int i=1;i<=n;i++)dx[i]=dep[i]%x;
    for (int i=0;i<x;i++)o[i]=0;
    for (int i=1;i<=n;i++)o[dx[tp[i]]]++;
    for (int i=1;i<=x;i++)o[i]+=o[i-1];
    for (int i=n;i;i--)p[o[dx[tp[i]]]--]=tp[i];
    T2.clear();
    for (int i=1;i<=n;i++)id[p[i]]=i;
    for (int i=1;i<=m;i++){
      if (b[i].op==1&&b[i].x==x){
        int l=lower_bound(p+o[b[i].y]+1,p+o[b[i].y+1]+1,b[i].u,cmp)-p,
            r=upper_bound(p+o[b[i].y]+1,p+o[b[i].y+1]+1,out[b[i].u],cmp)-p-1;
        if (l<=r){T2.add(l,b[i].c);T2.add(r+1,-b[i].c);}
      }else ans[i]+=T2.qry(id[b[i].u]);
    }
  }
  for (int i=1;i<=m;i++)
    if (b[i].op==2)
      printf("%d\n",ans[i]);
  return 0;
}

附送 : P3591 [POI2015]ODW