[Ynoi2077] stdmxeypz 解题报告

· · 题解

讲一种代码十分简短的做法（1.34k，目前(2022.9.17)是最短解）。

首先可以把子树操作变成 DFS 序上的操作，考虑对序列进行分块，设块的大小为 B1，对于散块，我们可以通过暴力维护，而对于整块，我们另外考虑方法。

我们发现整块直接维护比较困难，但考虑到有 \bmod x=y，这显然就是根号分治嘛，再设阈值 B2，当 x\le B2 的时候考虑直接在对应的块上面暴力打标记，考虑 x>B2 的时候怎么做。

我们考虑深度为 i 并且在第 j 个块的点的标记数组，显然当 x>B2 的时候我们可以直接暴力在对应深度上打标记，由于一横行只有 n/B1 个元素，所以我们可以先差分，查询的时候直接暴力查即可。

总复杂度 O(\frac{nq}{B1}+\frac{nq}{B2}+q(B1+B2))，正常来说是 B1=B2=\sqrt n 时比较优，但这样空间就是 2n^{1.5} 了，过不去，所以需要调整一下，我把 B1 调到了 1500，B2 调到了 200 就过了。

下面是代码（没加快读没卡常能过）

#include<cstdio>
#include<cmath>
using namespace std;
const int N=3e5+2,M=202;
int dep[N],dfn[N],cnt,id[N],s[N],B,B1;
struct edge{
    int next,to;
}e[N];
int first[N],len,T,n,siz[N],ans;
int t1[N][M],t2[M][M][M];
void add(int a,int b)
{
    e[++len]=edge{first[a],b};
    first[a]=len;
}
void BF(int l,int r,int x,int y,int z)
{
    for(int i=l;i<=r;i++)
        if(dep[i]%x==y) s[i]+=z;
}
void modify(int l,int r,int x,int y,int z)
{
    y%=x;
    if(id[l]==id[r]) BF(l,r,x,y,z);
    else
    {
        BF(l,id[l]*B,x,y,z);
        BF((id[r]-1)*B+1,r,x,y,z);
        if(x<=B1)
            for(int i=id[l]+1;i<id[r];i++)
                t2[i][x][y]+=z;
        else
            for(int i=y;i<=n;i+=x)
                t1[i][id[l]+1]+=z,t1[i][id[r]]-=z;
    }
}
void dfs(int x)
{
    siz[x]=1;
    for(int i=first[x],y;i;i=e[i].next)
        dep[dfn[y=e[i].to]=++cnt]=dep[dfn[x]]+1,dfs(y),siz[x]+=siz[y];
}
int a,x,y,z,op;
int main()
{
    scanf("%d%d",&n,&T);
    for(int i=2;i<=n;i++) scanf("%d",&x),add(x,i);
    dfn[cnt=1]=1,dfs(1);
    B=1500,B1=200;
    for(int i=1;i<=n;i++) id[i]=(i-1)/B+1;
    while(T--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d%d",&a,&x,&y,&z);
            modify(dfn[a],dfn[a]+siz[a]-1,x,dep[dfn[a]]+y,z);
        }
        else
        {
            scanf("%d",&x);
            ans=s[x=dfn[x]];
            for(int i=1;i<=id[x];i++)
                ans+=t1[dep[x]][i];
            for(int i=1;i<=B1;i++)
                ans+=t2[id[x]][i][dep[x]%i];
            printf("%d\n",ans);
        }
    }
}