Codeforces

Luogu

分析

考虑把每个询问拆成 $\sum_{i=1}^r\operatorname{dis}(p_i,u)-\sum_{i=1}^{l-1}\operatorname{dis}(p_i,u)$。

我们考虑怎么求 $\sum_{i=1}^t\operatorname{dis}(p_i,u)$,这个东西可以拆成 $t\times dep_u+\sum_{i=1}^t dep_{p_i}-2\sum_{i=1}^t dep_{\operatorname{LCA}(p_i,u)}$。

前两个很好维护,我们只要考虑求 $\sum_{i=1}^t dep_{\operatorname{LCA}(p_i,u)}$。

这是一个经典问题。我们把每个 $p_{1..t}$ 到根的路径全部加上 $1$,然后查询 $u$ 到根的路径的和即可。

这样子就可以直接树链剖分+可持久化线段树预处理,修改时可以发现只会修改第 $x$ 个版本,直接从上个版本重新修改一次即可。

因为有区间加,所以需要标记永久化。

然而空间可能开不下,有两个优化:第一个是在跳重链修改时不新建本次跳重链过程中新建的点,另一个是在修改达到一定次数时直接清空可持久化线段树然后重建。这样子就可以卡过去了。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,Q,p[N]; ll sum[N],pre[N];

struct edge { int v,w,nxt; } e[N<<1];
int head[N];
void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

int fa[N],sz[N],hson[N],top[N],fw[N]; ll dep[N];
int dfn[N],pos[N],tim=0;
void dfs1(int u,int f) {
    fa[u]=f,sz[u]=1;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==f) continue;
        fw[v]=w,dep[v]=dep[u]+w,dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim,pos[tim]=u;
    if (hson[u]) dfs2(hson[u],anc);
    for (int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}

#define ls(o) t[o].ls
#define rs(o) t[o].rs
int rt[N],tot=0,lim;
struct node { ll sumv; int addv,ls,rs;} t[N*150];
void modify(int& o,int l,int r,int ql,int qr) {
    if (o<=lim) t[++tot]=t[o],o=tot;
    if (ql<=l&&r<=qr) { t[o].sumv+=pre[r]-pre[l-1],++t[o].addv; return;    }
    int mid=(l+r)>>1;
    if (ql<=mid) modify(ls(o),l,mid,ql,qr);
    if (qr>mid) modify(rs(o),mid+1,r,ql,qr);
    t[o].sumv=t[ls(o)].sumv+t[rs(o)].sumv+t[o].addv*(pre[r]-pre[l-1]);
}
ll query(int o,int l,int r,int ql,int qr,int tag) {
    if (!o) return tag*(pre[min(r,qr)]-pre[max(l,ql)-1]);
    if (ql<=l&&r<=qr) return t[o].sumv+tag*(pre[r]-pre[l-1]);
    int mid=(l+r)>>1; ll res=0;
    if (ql<=mid) res+=query(t[o].ls,l,mid,ql,qr,tag+t[o].addv);
    if (qr>mid) res+=query(t[o].rs,mid+1,r,ql,qr,tag+t[o].addv);
    return res;
}
#undef ls
#undef rs

void modify(int u,int t) {
    lim=tot;
    while (u) {
        modify(rt[t],1,n,dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }
}
ll query(int u,int t) {
    ll res=t*dep[u]+sum[t];
    while (u) {
        res-=2*query(rt[t],1,n,dfn[top[u]],dfn[u],0);
        u=fa[top[u]];
    }
    return res;
}

int main() {
    n=read(),Q=read();
    for (int i=1;i<=n;++i) p[i]=read();
    for (int i=1;i<n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    dfs1(1,0),dfs2(1,1);
    for (int i=1;i<=n;++i) sum[i]=sum[i-1]+dep[p[i]];
    for (int i=1;i<=n;++i) pre[i]=pre[i-1]+fw[pos[i]];
    for (int i=1;i<=n;++i) rt[i]=rt[i-1],modify(p[i],i);
    int lastans=0,cnt=0;
    while (Q--) {
        int op=read();
        if (op==1) {
            int l=read()^lastans,r=read()^lastans,u=read()^lastans;
            ll ans=query(u,r)-query(u,l-1); printf("%lld\n",ans);
            lastans=ans&1073741823;
        } else {
            int x=read()^lastans;
            swap(p[x],p[x+1]),sum[x]=sum[x-1]+dep[p[x]];
            if (++cnt==50000) {
                cnt=tot=0;
                for (int i=1;i<=n;++i) rt[i]=rt[i-1],modify(p[i],i);
            }
            else rt[x]=rt[x-1],modify(p[x],x);
        }
    }
    return 0;
}
最后修改:2020 年 07 月 30 日 09 : 06 PM