题解：P8353 [SDOI/SXOI2022] 无处存储

concertb · 2026-07-23 10:50:48 · 题解

看题解区的树分块都是随机撒点，这里给出一个确定性树分块做法。

能够严格保证保证每个关键点到离它最近的祖先关键点的距离不超过 S。

64 MB 意味着长度为 n 的数组只能开两个，无法直接 DFS。利用 fa_i < i 的性质，逆序遍历即可非递归遍历，那 mrsrz 巨佬的关键数组 mxd 怎么办？

我们发现 mxd<BLK，其中 BLK 是块长。\forall fa_i <n <2^{23} =8388608。一个 unsigned int 有 32 位，那么低 24 位存父节点编号，高 8 位存 mxd 即可。（代码中 37 到 50 行部分）。

选好点后其他部分类似 Renshey 处理即可。复杂度一样。

link

:::info[Code]

#include<bits/stdc++.h>
#define int unsigned int
using namespace std;
namespace Fast_OI{
    char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
    #define putchar(x) (p3-obuf<1000000?*p3++=x:(fwrite(obuf,1,p3-obuf,stdout),p3=obuf,*p3++=x))
    int read(){
        int x=0;bool f=1;char c=getchar();
        while(!isdigit(c)){if(c=='-')f=0;c=getchar();}
        while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
        return f?x:-x;
    }
    void putstr(const char* str){
        while(*str!='\0')putchar(*str ++); 
        putchar('\n'); 
    }
    void write(int x){
        if(x<0)putchar('-'),x=-x;
        if(x>9)write(x/10);
        putchar(x%10+48);
    }
    void flush(){fwrite(obuf,1,p3-obuf,stdout); }
}using namespace Fast_OI;
const int N=7e6+5;
const int BLK=256;
const int M=N/BLK*2+5;
int n,q;
int fa[N],a[N];
bitset<N> vis,tag;
vector<int> p;
int pre[M],cur[M];
int anc[M],lst[M];
int dep[M],deg[M];
int sum[M],add[M];
pair<int,int> e[M];
inline int get_fa(int u){
    return fa[u]&0xFFFFFF;
}
inline int get_mxd(int u){
    return (fa[u]>>24)&0xFF;
}
inline void set_fa(int u,int f){
    fa[u]=(fa[u]&0xFF000000u)|(f&0xFFFFFFu);
    return;
}
inline void set_mxd(int u,int d){
    fa[u]=(fa[u]&0xFFFFFFu)|((d&0xFFu)<<24);
    return;
}
inline int id(int u){
    return lower_bound(p.begin(),p.end(),u)-p.begin();
}
inline int get_dep(int u){
    int d=0;
    while(!vis[u]){
        u=get_fa(u);
        ++d;
    }
    return d+dep[id(u)];
}
inline int find(int u){
    while(!vis[get_fa(u)])
        u=get_fa(u);
    int k=id(get_fa(u));
    int l=pre[k],r=pre[k+1]-1;
    while(l<=r){
        int mid=l+r>>1;
        if(e[mid].first==u)
            return e[mid].second;
        if(e[mid].first<u)
            l=mid+1;
        else r=mid-1;
    }
    return -1;
}
inline void upd(int u,int w){
    if(!u)  return;
    while(!tag[u]){
        a[u]+=w;
        u=get_fa(u);
    }
    if(!vis[u]){
        int x=find(u),y=anc[x];
        for(int v=p[x];v!=p[y];v=get_fa(v))
            a[v]+=add[x];
        for(int v=u;v!=p[y];v=get_fa(v))
            a[v]+=w,sum[x]+=w;
        add[x]=0;
        u=p[y];
    }
    for(int i=id(u);i;i=anc[i]){
        sum[i]+=w*(dep[i]-dep[anc[i]]);
        add[i]+=w;
    }
    return;
}
inline int qry(int u){
    if(!u)  return 0;
    int res=0;
    while(!tag[u]){
        res+=a[u];
        u=get_fa(u);
    }
    if(!vis[u]){
        int x=find(u),y=anc[x];
        for(int v=p[x];v!=p[y];v=get_fa(v))
            a[v]+=add[x];
        for(int v=u;v!=p[y];v=get_fa(v))
            res+=a[v];
        add[x]=0;
        u=p[y];
    }
    for(int i=id(u);i;i=anc[i])
        res+=sum[i];
    return res;
}
inline int LCA(int u,int v){
    while(u!=v)
        if(dep[u]<dep[v])
            v=anc[v];
        else    u=anc[u];
    return u;
}
inline int lca(int u,int v){
    int x=u,y=v,du=get_dep(u),dv=get_dep(v);
    while(!tag[x])  x=get_fa(x);
    while(!tag[y])  y=get_fa(y);
    if(x==y){
        while(u!=v)
            if(du<dv)
                v=get_fa(v),dv--;
            else    u=get_fa(u),du--;
        return u;
    }
    u=x;
    if(vis[x])
        x=id(x);
    else    x=find(x);
    v=y;
    if(vis[y])
        y=id(y);
    else    y=find(y);
    if(x==y)
        if(get_dep(u)<get_dep(v))
            return u;
        else    return v;
    int z=LCA(x,y);
    if(z==x)
        return u;
    if(z==y)
        return v;
    return p[z];
}
inline void upd(int u,int v,int w){
    if(u==v){
        upd(u,w);
        upd(get_fa(u),-w);
        return;
    }
    int l=lca(u,v);
    if(l==u){
        upd(v,w);
        upd(get_fa(u),-w);
        return;
    }
    if(l==v){
        upd(u,w);
        upd(get_fa(v),-w);
        return;
    }
    upd(u,w),upd(v,w);
    upd(l,-w),upd(get_fa(l),-w);
    return;
}
int qry(int u,int v){
    if(u==v)
        return qry(u)-qry(get_fa(u));
    int l=lca(u,v);
    if(l==u)
        return qry(v)-qry(get_fa(u));
    if(l==v)
        return qry(u)-qry(get_fa(v));
    return qry(u)+qry(v)-qry(l)-qry(get_fa(l));
}
signed main(){
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
    read(),n=read(),q=read();
    int A=read(),B=read(),C=read();
    a[0]=read();
    for(int i=1;i<=n;i++)
        a[i]=A*a[i-1]*a[i-1]+B*a[i-1]+C;
    for(int i=2;i<=n;i++){
        int f=read();
        set_fa(i,f);
    }
    set_fa(1,0);
    for(int i=1;i<=n;i++)
        set_mxd(i,1);
    for(int i=n;i>=2;--i){
        int f=get_fa(i);
        int d=get_mxd(i)+1;
        if(d>get_mxd(f)){
            set_mxd(f,d);
            if(d>=BLK){
                vis[f]=1;
                set_mxd(f,1);
            }
        }
    }
    vis[1]=1;
    p.clear();
    for(int i=1;i<=n;i++)
        if(vis[i])
            p.push_back(i);
    for(size_t i=0;i<p.size();i++){
        int u=p[i];
        while(!tag[u]){
            tag[u]=1;
            u=get_fa(u);
        }
        if(!vis[u]){
            vis[u]=1;
            p.push_back(u);
        }
    }
    sort(p.begin(),p.end());
    int m=p.size();
    sum[0]=a[1];
    dep[0]=1;
    anc[0]=0;
    for(int i=1;i<m;i++){
        sum[i]=a[p[i]];
        dep[i]=1;
        anc[i]=get_fa(p[i]);
        lst[i]=p[i];
        while(!vis[anc[i]]){
            sum[i]+=a[anc[i]];
            ++dep[i];
            lst[i]=anc[i];
            anc[i]=get_fa(anc[i]);
        }
    }
    for(int i=1;i<m;i++){
        anc[i]=id(anc[i]);
        dep[i]+=dep[anc[i]];
        ++deg[anc[i]];
    }
    for(int i=0;i<m;i++)
        pre[i+1]=pre[i]+deg[i];
    for(int i=0;i<=m;i++)
        cur[i]=pre[i];
    for(int i=1;i<m;i++)
        e[cur[anc[i]]++]={lst[i],i};
    for(int i=0;i<m;i++)
        if(pre[i]<pre[i+1])
            sort(e+pre[i],e+pre[i+1]);
    int ans=0;
    while(q--){
        int op=read();
        int u=read()^ans,v=read()^ans;
        if(op==0){
            int w=read()^ans;
            upd(u,v,w);
        }
        if(op==1){
            ans=qry(u,v);
            write(ans),putchar('\n');
            ans&=(1<<20)-1;
        }
    }
    flush();
    return 0;
}

:::