【Ynoi2012】WC,THUWC,CTSC与APIO2017

mrsrz 11月 02, 2019

根号分治+序列分块+操作分块

题目大意：

给定一棵树，有两个操作：

给定 $a,x,y,z$，将 $a$ 的子树中与 $a$ 的距离模 $x$ 等于 $y$ 的结点的权值加上 $z$。
给定 $a$，询问 $a$ 的点权。

题解：

首先对 $x$ 进行根号分治。

对 $x\leq\sqrt n$ 的部分，我们对树按照 dfs 序进行序列分块，每个块内维护数组 $s[x][y]$ 表示这个块内所有深度模 $x$ 余 $y$ 的数被整体加上了多少。修改时，边角暴力判断并修改点权，中间的直接修改 $s$ 数组。查询时，枚举 $x$ 然后累加所在块的答案即可。修改、查询的时间复杂度均为 $O(\sqrt n)$。空间复杂度 $O(n\sqrt n)$。

对 $x\geq \sqrt n$ 的部分，我们离线后进行操作分块。把每 $\sqrt n$ 个操作和询问放到一块。对整块操作进行处理时，如果是查询，则枚举这个操作块中在它之前的修改操作，并在原有答案基础上把这些修改的贡献加上。如果是修改，则在 dfs 序上的对应深度处打差分标记，等处理完这整块操作后，对其进行线性的扫描，把贡献直接加到点上。

这部分单次复杂度 $O(n)$，总复杂度 $O(n\sqrt n)$。

所以整个算法的时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n\sqrt n)$。实际块大小还需要根据时空限制进行合理调整。

Code：

#include<cstdio>
#include<cctype>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=3e5+5,lim=300,siz=660;
int n,m,head[N],cnt,sz[N],fa[N],dep[N];
int dfn[N],idfn[N],idx,L[N],R[N],blocks;
int s[N/siz+2][lim+2][lim+2],add[N],dlt[N];
vector<int>up[N],down[N];
inline int bel(int x){return(x-1)/siz+1;}
inline int readint(){
    int c=getchar(),d=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())d=d*10+(c^'0');
    return d;
}
struct edge{
    int to,nxt;
}e[N];
struct que{
    int op,a,x,y,v;
}q[800];
struct mdf{
    int id,a,x,y,v;
    inline bool operator<(const mdf&rhs)const{return id<rhs.id;}
};
vector<mdf>vec;
int top;
void dfs(int now){
    idfn[dfn[now]=++idx]=now;
    sz[now]=1;
    for(int i=head[now];i;i=e[i].nxt){
        dep[e[i].to]=dep[now]+1;fa[e[i].to]=now;
        dfs(e[i].to);
        sz[now]+=sz[e[i].to];
    }
}
void modify(int l,int r,int x,int y,int v){
    const int bL=bel(l),bR=bel(r);
    if(bL==bR)for(int i=l;i<=r;++i){
        if(dep[idfn[i]]%x==y)add[i]+=v;
    }else{
        for(int i=l;i<=R[bL];++i)
        if(dep[idfn[i]]%x==y)add[i]+=v;
        for(int i=L[bR];i<=r;++i)
        if(dep[idfn[i]]%x==y)add[i]+=v;
        for(int i=bL+1;i<bR;++i)
        s[i][x][y]+=v;
    }
}
void solve(){
    memset(dlt,0,sizeof dlt);
    vec.clear();
    for(int i=1;i<=top;++i)
    if(q[i].op==2){
        int t=q[i].a,ans=q[i].x;
        for(int j=1;j<i;++j)
        if(q[j].op==1){
            int rt=q[j].a,x=q[j].x,y=q[j].y,v=q[j].v;
            if(dfn[rt]<=dfn[t]&&dfn[t]<=dfn[rt]+sz[rt]-1&&(dep[t]-dep[rt])%x==y)
            ans+=v;
        }
        printf("%d\n",ans);
    }else{
        int a=q[i].a,y=q[i].y,x=q[i].x;
        vec.push_back((mdf){dfn[a],a,x,y,q[i].v});
        vec.push_back((mdf){dfn[a]+sz[a],a,x,y,-q[i].v});
    }
    top=0;
    sort(vec.begin(),vec.end());
    for(int i=1,it=0;i<=n;++i){
        while(it<vec.size()&&vec[it].id==i){
            int a=vec[it].a,x=vec[it].x,y=vec[it].y,v=vec[it].v;
            for(int deep=dep[a]+y;deep<=n;deep+=x)dlt[deep]+=v;
            ++it;
        }
        add[i]+=dlt[dep[idfn[i]]];
    }
}
int main(){
    n=readint(),m=readint();
    for(int i=2;i<=n;++i){
        int v=readint();
        e[++cnt]=(edge){i,head[v]},head[v]=cnt;
    }
    dfs(dep[1]=1);
    blocks=(n-1)/siz+1;
    for(int i=1;i<=blocks;++i)R[i]=i*siz,L[i]=R[i-1]+1;R[blocks]=n;
    while(m--){
        int op=readint();
        if(op==1){
            int a=readint(),x=readint(),y=readint(),v=readint();
            if(x<=lim)modify(dfn[a],dfn[a]+sz[a]-1,x,(y+dep[a])%x,v);
            else q[++top]=(que){1,a,x,y,v};
        }else{
            int a=readint();
            int ans=add[dfn[a]];
            auto&x=s[bel(dfn[a])];
            for(int j=1;j<=lim;++j)
            ans+=x[j][dep[a]%j];
            q[++top]=(que){2,a,ans};
        }
        if(top==650)solve();
    }
    if(top)solve();
    return 0;
}