题解 CF757G 【Can Bash Save the Day?】

· · 题解 

现有的题解里一篇是动态点分治的题解，另一篇介绍了可持久化线段树的做法但不甚详尽。本文将详细分析后一种做法。

首先我们观察一下询问的特点。

不妨钦定1为根节点。假设我们预处理出了树上每个点i的深度（也就是i到根节点的距离）dep_i，记节点i,j的最近公共祖先为\text{LCA}(i,j)，记i,j路径长度为\text{DIST}(i,j)，那么很明显有：

\text{DIST}(i,j)=dep_i+dep_j-2dep_{\text{LCA}(i,j)}

那么分析题中询问式，很容易想到拆成两个前缀的差值，换言之，只要对于给定的u,v，我们能求出\sum_{i=1}^u\text{DIST}(p_i,v)，就可以轻易解决原问题。

而

\sum_{i=1}^u\text{DIST}(p_i,v) =\sum_{i=1}^u(dep_{p_i}+dep_v-2dep_{\text{LCA}(p_i,v)}) =u\times dep_v +(\sum_{i=1}^udep_{p_i})-2(\sum_{i=1}^udep_{\text{LCA}(p_i,v)})

在修改的时候，式子的第一部分值u\times dep_v为一个常量，第二部分\sum_{i=1}^udep_{p_i}开一个数组sumdep_u维护，当交换p_x,p_{x+1}修改时只需修改sumdep_x即可，这两部分的维护都非常简单。我们重点分析第三部分\sum_{i=1}^udep_{\text{LCA}(p_i,v)}的维护过程。

关键问题是：如何转换dep_{\text{LCA}(p,v)}？考虑这样一个模型：树上每条边e有一个附加权值cnt_e代表访问次数，我们把p到根节点的路径上的cnt_e置为1，再访问v到根节点路径上的每条边e，计算\sum cnt_e\times w_e即为答案（其中w_e代表边e的长度）。

这个模型明显具有可加性，也就是说，为了计算\sum_{i=1}^udep_{\text{LCA}(p_i,v)}，对于每个1\leq i\leq u，我们把位于p_i和根路径节点上的边的cnt都加1，然后按上述方法计算，就可以得到\sum_{i=1}^udep_{\text{LCA}(p_i,v)}的值了。

问题又转变成了：如何快速在树上执行路径加、路径求和操作？又如何对于每个节点u都维护好cnt_e？

前一个问题的答案是树链剖分，后一个问题的答案是可持久化线段树。

由于边在程序中不好表示，我们把边上的问题转移到点上：对于每条边，我们转移到该边的下方节点上维护。也就是说，对于每个节点i，我们预处理出它和父亲之间的边的边权val_i，特别地，令val_1=0。这样我们就可以方便地维护边权。

梳理一下，对于每个新点的加入，操作步骤如下：

但普通的可持久化线段树不支持区间加操作，对此有下列两种方法：

方法一：差分

在线段树上维护所有dif_i=cnt_i-cnt_{i-1}的值，则原来的区间修改变成了单点修改，可以可持久化。

而此时cnt_i=\sum_{j=1}^idif_j，则要维护的\sum_{i=1}^tcnt_ival_i=\sum_{i=1}^tval_i\sum_{j=1}^idif_j=\sum_{j=1}^tdif_j\sum_{i=j}^jval_j，预处理出s_i=\sum_{j=1}^ival_j，则原式化为\sum_{j=1}^tdif_j(s_t-s_{j-1})，其中s_t是常量，故分开维护\sum dif_j和\sum s_{j-1}dif_j即可。

这个方法效率不佳，空间复杂度较高，目前不能通过本题的数据。各位大佬可以帮忙调一下下面的代码：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

int n=0,q=0;

int p[250000];
struct e
{
    int to,val;e(int t=0,int v=0):to(t),val(v){} 
};
vector<e> ed[250000];

int fa[250000],sz[250000],son[250000];long long dep[250000],val[250000];
void dfs_bas(int u,int f)
{
    fa[u]=f,sz[u]=1,son[u]=0;
    for(int i=0;i<ed[u].size();i++)
    {
        int v=ed[u][i].to;
        if(v!=f)
        {
            dep[v]=dep[u]+ed[u][i].val,val[v]=ed[u][i].val;
            dfs_bas(v,u);
            sz[u]+=sz[v];
            if(sz[v]>sz[son[u]])son[u]=v;
        }
    }
}

int seg[250000],rev[250000],top[250000];
void dfs_sec(int pos=1,int f=0)
{
    if(son[pos])
    {
        seg[0]++;seg[son[pos]]=seg[0];
        top[son[pos]]=top[pos];
        rev[seg[0]]=son[pos];
        dfs_sec(son[pos],pos);
    }
    for(int i=0,v=0;i<ed[pos].size();i++)
    {
        v=ed[pos][i].to;
        if(v!=son[pos]&&v!=f)
        {
            seg[0]++;seg[v]=seg[0];
            rev[seg[0]]=v;
            top[v]=v;
            dfs_sec(v,pos);
        }
    }
}
long long s[250000];

struct nd
{
    int lch,rch;int sum;long long sum_s;
};
nd t[32000001];

int used=0;
void build(int l,int r,int &k)
{
    if(!k)k=++used;
    t[k].lch=t[k].rch=0;
    if(l==r)
    {
        t[k].sum=t[k].sum_s=0;return;
    }
    int mid=(l+r)>>1;
    build(l,mid,t[k].lch),build(mid+1,r,t[k].rch);
    t[k].sum=t[t[k].lch].sum+t[t[k].rch].sum,t[k].sum_s=t[t[k].lch].sum_s+t[t[k].rch].sum;
}

int change(int now,int l,int r,int pos,int val,int old)
{
    if(pos<1||pos>n)return now;

    int p;
    if(now==old)
    {
        p=++used;t[p]=t[now];
    }
    else
    {
        p=now;
    }
    if(l==r)
    {
        t[p].sum+=val,t[p].sum_s+=s[pos-1]*val;return p;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
    {
        t[p].lch=change(t[now].lch,l,mid,pos,val,t[old].lch);
        t[p].sum=t[t[p].lch].sum+t[t[p].rch].sum,t[p].sum_s=t[t[p].lch].sum_s+t[t[p].rch].sum_s;
    }
    else
    {
        t[p].rch=change(t[now].rch,mid+1,r,pos,val,t[old].rch);
        t[p].sum=t[t[p].lch].sum+t[t[p].rch].sum,t[p].sum_s=t[t[p].lch].sum_s+t[t[p].rch].sum_s;
    }
    return p;
}
long long query_sum(int now,int l,int r,int x,int y)
{
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return t[now].sum;
    int mid=(l+r)/2;
    return query_sum(t[now].lch,l,mid,x,y)+query_sum(t[now].rch,mid+1,r,x,y);
}
long long query_sum_s(int now,int l,int r,int x,int y)
{
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return t[now].sum_s;
    int mid=(l+r)/2;
    return query_sum_s(t[now].lch,l,mid,x,y)+query_sum_s(t[now].rch,mid+1,r,x,y);
}

int rt[250000];
int add_road(int tree_id,int pos,int val)
{
    int fpos=0;int k=rt[tree_id];
    while(pos)
    {
        fpos=top[pos];
        k=change(k,1,n,seg[fpos],val,rt[tree_id]);
        k=change(k,1,n,seg[pos]+1,-val,rt[tree_id]);
        pos=fa[fpos];
    }
    return k;
}

long long query_single(int tree_id,int k)
{
    long long sum=query_sum(rt[tree_id],1,n,1,k),sum_s=query_sum_s(rt[tree_id],1,n,1,k);
    return sum*s[k]-sum_s;
}
long long query_point(int tree_id,int pos)
{
    int fpos=0;long long sum=0;
    while(pos)
    {
        fpos=top[pos];
        sum+=query_single(tree_id,seg[pos])-query_single(tree_id,seg[fpos]-1);
        pos=fa[fpos];
    }
    return sum;
}

long long sum_dep[250000];

long long sum_dist(int tree_id,int v)
{
    return sum_dep[tree_id]+dep[v]*tree_id-2*query_point(tree_id,v);
}

int main()
{
    scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    for(int i=1,x=0,y=0,w=0;i<n;i++){scanf("%d%d%d",&x,&y,&w);ed[x].push_back(e(y,w)),ed[y].push_back(e(x,w));}

    dfs_bas(1,0);
    seg[0]=seg[1]=top[1]=rev[1]=1;dfs_sec(1);
    for(int i=1;i<=n;i++)s[i]=s[i-1]+val[rev[i]];

    build(1,n,rt[0]);
    for(int i=1;i<=n;i++)rt[i]=add_road(i-1,p[i],1);
    for(int i=1;i<=n;i++)sum_dep[i]=sum_dep[i-1]+dep[p[i]];
    int type=0,l=0,r=0,v=0,x=0;
    long long last_ans=0;
    int cnt=0;
    while(q--)
    {
        scanf("%d",&type);
        if(type==1)
        {
            scanf("%d%d%d",&l,&r,&v);
            l=last_ans^l,r=last_ans^r,v=last_ans^v;
            last_ans=sum_dist(r,v)-sum_dist(l-1,v);

            printf("%lld\n",last_ans);
            last_ans%=1<<30;
        }
        else
        {
            cnt++;
            scanf("%d",&x);
            x=last_ans^x;
            sum_dep[x]=sum_dep[x-1]+dep[p[x+1]];
            if(used>3e7)
            {
                swap(p[x],p[x+1]);
                used=0;
                memset(rt,0,sizeof(rt));build(1,n,rt[0]);
                for(int i=1;i<=n;i++)rt[i]=add_road(i-1,p[i],1);
                cnt=0;
            }
            else
            {
                rt[x]=add_road(x-1,p[x+1],1);
                swap(p[x],p[x+1]);
            }
        }
    }
}

方法二：标记永久化

其实可持久化线段树区间修改问题更常用的方法是标记永久化。不会的可以自行搜索这题的题解。代码：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

int n=0,q=0;

int p[250000];
struct e
{
    int to,val;e(int t=0,int v=0):to(t),val(v){} 
};
vector<e> ed[250000];

int fa[250000],sz[250000],son[250000];long long dep[250000],val[250000];
void dfs_bas(int u,int f)
{
    fa[u]=f,sz[u]=1,son[u]=0;
    for(int i=0;i<ed[u].size();i++)
    {
        int v=ed[u][i].to;
        if(v!=f)
        {
            dep[v]=dep[u]+ed[u][i].val,val[v]=ed[u][i].val;
            dfs_bas(v,u);
            sz[u]+=sz[v];
            if(sz[v]>sz[son[u]])son[u]=v;
        }
    }
}

int seg[250000],rev[250000],top[250000];
void dfs_sec(int pos=1,int f=0)
{
    if(son[pos])
    {
        seg[0]++;seg[son[pos]]=seg[0];
        top[son[pos]]=top[pos];
        rev[seg[0]]=son[pos];
        dfs_sec(son[pos],pos);
    }
    for(int i=0,v=0;i<ed[pos].size();i++)
    {
        v=ed[pos][i].to;
        if(v!=son[pos]&&v!=f)
        {
            seg[0]++;seg[v]=seg[0];
            rev[seg[0]]=v;
            top[v]=v;
            dfs_sec(v,pos);
        }
    }
}
long long s[250000];

struct nd
{
    int lch,rch;int sum;long long sum_s;
};
nd t[30000001];

int used=0,lim=0;
void change(int &now,int l,int r,int x,int y)
{
    if(now<=lim)
    {
        ++used;t[used]=t[now];now=used;
    }
    int mid=(l+r)>>1;
    if(x<=l&&r<=y)
    {
        t[now].sum++;t[now].sum_s+=s[r]-s[l-1];return;
    }
    if(x<=mid)change(t[now].lch,l,mid,x,y);
    if(y>mid)change(t[now].rch,mid+1,r,x,y);
    t[now].sum_s=t[t[now].lch].sum_s+t[t[now].rch].sum_s+(s[r]-s[l-1])*t[now].sum;
}
long long query(int now,int l,int r,int x,int y,int cnt)
{
    if(now==0)return cnt*(s[min(r,y)]-s[max(l,x)-1]);
    if(x<=l&&r<=y)return t[now].sum_s+cnt*(s[r]-s[l-1]);
    int mid=(l+r)>>1;
    long long ans=0;
    if(x<=mid)ans+=query(t[now].lch,l,mid,x,y,cnt+t[now].sum);
    if(y>mid)ans+=query(t[now].rch,mid+1,r,x,y,cnt+t[now].sum);
    return ans;
}

int rt[250000];
void add_road(int tree_id,int pos)
{
    lim=used;
    int fpos=0;
    while(pos)
    {
        fpos=top[pos];
        change(rt[tree_id],1,n,seg[fpos],seg[pos]);
        pos=fa[fpos];
    }
}

long long sum_dep[250000];

long long sum_dist(int tree_id,int v)
{
    int pos=v,fpos=0;long long sum=0;
    while(pos)
    {
        fpos=top[pos];
        sum+=query(rt[tree_id],1,n,seg[fpos],seg[pos],0);
        pos=fa[fpos];
    }
    return sum_dep[tree_id]+dep[v]*tree_id-2*sum;
}

int main()
{
    scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    for(int i=1,x=0,y=0,w=0;i<n;i++){scanf("%d%d%d",&x,&y,&w);ed[x].push_back(e(y,w)),ed[y].push_back(e(x,w));}

    dfs_bas(1,0);
    seg[0]=seg[1]=top[1]=rev[1]=1;dfs_sec(1);
    for(int i=1;i<=n;i++)s[i]=s[i-1]+val[rev[i]];
    for(int i=1;i<=n;i++)rt[i]=rt[i-1],add_road(i,p[i]);
    for(int i=1;i<=n;i++)sum_dep[i]=sum_dep[i-1]+dep[p[i]];

    int type=0,l=0,r=0,v=0,x=0;
    long long last_ans=0;
    int cnt=0;
    while(q--)
    {
        scanf("%d",&type);
        if(type==1)
        {
            scanf("%d%d%d",&l,&r,&v);
            l=last_ans^l,r=last_ans^r,v=last_ans^v;
            last_ans=sum_dist(r,v)-sum_dist(l-1,v);

            printf("%lld\n",last_ans);
            last_ans%=1<<30;
        }
        else
        {
            cnt++;
            scanf("%d",&x);
            x=last_ans^x;
            sum_dep[x]=sum_dep[x-1]+dep[p[x+1]];
            if(used>2.99e7)
            {
                swap(p[x],p[x+1]);
                used=0;
                for(int i=1;i<=n;i++)rt[i]=rt[i-1],add_road(i,p[i]);
                cnt=0;
            }
            else
            {
                rt[x]=rt[x-1];add_road(x,p[x+1]);
                swap(p[x],p[x+1]);
            }
        }
    }
}