P10107 题解

· · 题解

考虑按位计算贡献，先考虑链的情况。考虑倍增，设 f_{i,k} 表示 [i,i+2^k) 区间的答案。转移时先累加两个小区间的贡献，另外后半部分的第 (k-1) 位要异或 1，因此设 g_{i,k} 表示前 i 个数第 k 位若异或 1 会产生的总变化量。统计时若其该位为 1 则贡献 -1，否则贡献 1。通过差分计算变化量，最终转移为 f_{i,k}=f_{i,k-1}+f_{i+2^{k-1},k-1}+2^{k-1}\times(g_{i+2^k-1}-g_{i+2^{k-1}-1})。统计答案时一直向后跳并累加即可。

考虑把这东西搬到树上，但由于子树内在某一层上的点不止一个，只能在 i 节点本身上记录信息。所以设 f_{i,j,k} 表示 i 子树内深度在 [d_i+j,d_i+j+2^k) 内所有点的贡献和。可以发现这个 (i,j) 很能长链剖分，重儿子直接继承，轻儿子对应位置直接累加。但是这样没有计算 f_{i,0}，考虑怎么计算这个。

那么先把 a_i 加到 f_{i,0} 里。假如从子树 v 给 f_{i,0} 更新，设 s_k 表示 v 子树内对 f_{i,0,k} 的贡献，有 s_0=0。发现 s_k 可以用 s_{k-1} 拼上 f_{v,2^{k-1}-1,k-1} 得到，这里的式子应该和链的情况一样，实际实现时由于 s_k 只从 s_{k-1} 转移，开一个变量，一直更新就行。

那么问题就在于还需要一个记录贡献变化量的数组 g 来辅助更新。链上我们是用前缀和维护的，但是树上长剖不好搞前缀和，所以考虑转而计算后缀和。具体地设 g_{i,j,k} 表示 i 子树内深度不低于 d_i+j 的所有点权第 k 位若异或 1 会产生的总变化量，这就可以直接对应位累加了，只需要在 g_{i,0} 上额外加入 a_i 的贡献即可。

所有的转移和统计答案都跟链上类似，把每个询问扔到对应节点上处理即可。只是要格外注意在 g 上差分时不能超出当前节点的管辖范围，有比较多的细节。时间复杂度 O((n+q)\log n)。

#include<iostream>
#include<vector>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int N=1e6+10;
const int K=20+3;
int n,q,v[N],d[N],son[N]; ll res[N];
vector <int> e[N];
vector <pii> a[N];
struct nod{ll f[K],g[K];}temp[N],*f[N],*cur=temp;
void dfs(int u)
{
    d[u]=0;
    for(int v:e[u])
    {
        dfs(v),d[u]=max(d[u],d[v]);
        if(d[v]>d[son[u]]) son[u]=v;
    }
    d[u]++;
}
void merg(int u,int v)
{
    for(int j=0;j<20;j++) f[u][0].g[j]+=f[v][0].g[j];
    ll s=0;
    for(int p=0,k=1;k<20;p+=(1<<(k-1)),k++)
    {
        if(p<d[v]) s+=f[v][p].f[k-1]+(1<<(k-1))*f[v][p].g[k-1];
        if(p+(1<<(k-1))<d[v]) s-=(1<<(k-1))*f[v][p+(1<<(k-1))].g[k-1];
        f[u][0].f[k]+=s;
    }
}
void dfsb(int u)
{
    for(int j=0;j<20;j++) f[u][0].f[j]=v[u],f[u][0].g[j]=(((v[u]>>j)&1)?-1:1);
    if(son[u]) f[son[u]]=f[u]+1,dfsb(son[u]),merg(u,son[u]);
    for(int v:e[u]) if(v!=son[u])
    {
        f[v]=cur,cur+=d[v],dfsb(v),merg(u,v);
        for(int j=0;j<d[v];j++) for(int k=0;k<20;k++) 
            f[u][j+1].f[k]+=f[v][j].f[k],f[u][j+1].g[k]+=f[v][j].g[k];
    }
    for(pii te:a[u])
    {
        int x=min(te.first,d[u]-1),id=te.second;
        for(int p=0,k=19;k>=0;k--)
        {
            if(p+(1<<k)-1>x) continue;
            res[id]+=f[u][p].f[k],p+=(1<<k);
            if(p<d[u]) res[id]+=(1<<k)*f[u][p].g[k];
            if(x+1<d[u]) res[id]-=(1<<k)*f[u][x+1].g[k];
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n,d[0]=-1;
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=2,x;i<=n;i++) cin>>x,e[x].push_back(i);
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int x,k; cin>>x>>k;
        a[x].push_back({k,i});
    }
    dfs(1),f[1]=cur,cur+=d[1],dfsb(1);
    for(int i=1;i<=q;i++) cout<<res[i]<<'\n';
    return 0;
}