M_sea

洛谷4211 [LNOI2014]LCA
LuoguBZOJ分析考虑 $\sum\limits_{l\leq i\leq r}dep[LCA(i,z)]$ ...
扫描右侧二维码阅读全文
29
2019/04

洛谷4211 [LNOI2014]LCA

Luogu

BZOJ

分析

考虑 $\sum\limits_{l\leq i\leq r}dep[LCA(i,z)]$ 怎么快速求。

对于每个 $i\in[l,r]$ ,把 $1$ 到 $i$ 路径上经过的所有点的权值 $+1$ 。那么 $1$ 到 $z$ 路径上所有点的权值和就是答案。

正确性可以画个图感性理解一下。

这样做的话,复杂度是 $O(Qn\log n)$ 。

考虑怎么优化掉那个 $Q$ 。

首先把所有询问差分,变为 $\sum\limits_{1\leq i\leq r}dep[LCA(i,z)]-\sum\limits_{1\leq i\leq l-1}dep[LCA(i,z)]$ ,也就是拆成两个询问。

那么把拆出来的 $2Q$ 个询问离线,按右端点排序后将每个点依次加入并顺便计算答案即可。

具体实现及细节见代码。

这题代码怎么比宝牌一大堆还短

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline 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=100000+10;
const int mod=201314;

int n,Q;

struct Edge { int v,nxt; } e[N];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

struct Query { int x,z,id,w; } q[N];
bool operator <(Query a,Query b) { return a.x<b.x; }
int tot=0;

int dep[N],fa[N],sz[N],hson[N],top[N],dfn[N],tim=0;

inline void dfs1(int u,int f) {
    dep[u]=dep[f]+1,fa[u]=f,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u); sz[u]+=sz[v];
        if (!hson[u]||sz[v]>sz[hson[u]]) hson[u]=v;
    }
}

inline void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim;
    if (!hson[u]) return;
    dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
    }
}

struct Segment_Tree {
#define ls (o<<1)
#define rs (o<<1|1)
    
    int add[N<<2],sum[N<<2];
    
    inline void pushup(int o) { sum[o]=(sum[ls]+sum[rs])%mod; }
    inline void pushdown(int o,int l,int r) {
        if (add[o]) {
            int mid=(l+r)>>1;
            add[ls]+=add[o],add[rs]+=add[o];
            sum[ls]=(sum[ls]+(mid-l+1)*add[o])%mod;
            sum[rs]=(sum[rs]+(r-mid)*add[o])%mod;
            add[o]=0;
        }
    }

    inline void update(int o,int l,int r,int ql,int qr,int w) {
        if (ql<=l&&r<=qr) {
            add[o]+=w,sum[o]=(sum[o]+w*(r-l+1))%mod;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(o,l,r);
        if (ql<=mid) update(ls,l,mid,ql,qr,w);
        if (qr>mid) update(rs,mid+1,r,ql,qr,w);
        pushup(o);
    }
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return sum[o];
        int mid=(l+r)>>1,res=0;
        pushdown(o,l,r);
        if (ql<=mid) res=(res+query(ls,l,mid,ql,qr))%mod;
        if (qr>mid) res=(res+query(rs,mid+1,r,ql,qr))%mod;
        pushup(o);
        return res;
    }

#undef ls
#undef rs
} T;

inline void modify(int u,int v) {
    int tu=top[u],tv=top[v];
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
        T.update(1,1,n,dfn[tu],dfn[u],1);
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    T.update(1,1,n,dfn[v],dfn[u],1);
}

inline int query(int u,int v) {
    int tu=top[u],tv=top[v],res=0;
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
        res=(res+T.query(1,1,n,dfn[tu],dfn[u]))%mod;
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    res=(res+T.query(1,1,n,dfn[v],dfn[u]))%mod;
    return res;
}

int ans[N];

int main() {
    n=read(),Q=read();
    for (re int i=2;i<=n;++i) addEdge(read()+1,i);
    dfs1(1,0); dfs2(1,1);
    for (re int i=1;i<=Q;++i) {
        int l=read()+1,r=read()+1,z=read()+1;
        q[++tot]=(Query){l-1,z,i,-1};
        q[++tot]=(Query){r,z,i,1};
    }
    sort(q+1,q+tot+1);
    for (re int i=1,j=1;i<=tot;++i) {
        if (!q[i].x) continue;
        while (j<=q[i].x) modify(1,j),++j;
        ans[q[i].id]=(ans[q[i].id]+q[i].w*query(1,q[i].z)+mod)%mod;
    }
    for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]%mod);
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 01 PM

发表评论