[LNOI2014]LCA（树链剖分+线段树）

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3626

题解：看到LCA，我们可以直接想到这题的正解不是LCA！（LCA只能得20分，还要卡常）
于是我们怎么做呢？
考虑如何求Σdep[lca(i,z)](i∈[l,r])，由于不强制在线，我们不妨考虑离线……考虑每个lca贡献的答案。很显然z的lca在路径[1,z]上，所以我们可以把每一个lca到根的路径中所有点权值都加1，再从z跑一遍加上路径上的点的贡献即可。对于[l,r]，可以枚举i，然后i~根路径+1，跑一遍就行了，但这样会TLE，怎么办？很显然就是把[l,r]视为[1,l-1]和[1,r]两部分，答案就是第二部分减去第一部分的值，然后只要开一个vector。从1~n扫一遍然后覆盖，对当前节点vector内的询问做一下query就行了

#include<bits/stdc++.h>

#define lson l,mid,rt*2

#define rson mid+1,r,rt*2+1

using namespace std;

const int N=5e4+,mod=;

struct node{int id,v,z;};

vector<node>S[N];

vector<int>G[N];

int n,q,cnt,fa[N],sz[N],dep[N],son[N],id[N],top[N],ans[N],sum[N*],lazy[N*];

void dfs(int u)

{

    sz[u]=;

    for(int i=;i<G[u].size();i++)

    {

        fa[G[u][i]]=u,dep[G[u][i]]=dep[u]+;

        dfs(G[u][i]);

        sz[u]+=sz[G[u][i]];

        if(sz[son[u]]<sz[G[u][i]])son[u]=G[u][i];

    }

}

void dfs2(int u,int tp)

{

    id[u]=++cnt,top[u]=tp;

    if(son[u])dfs2(son[u],tp);

    for(int i=;i<G[u].size();i++)

    if(G[u][i]!=son[u])dfs2(G[u][i],G[u][i]);

}

void pushdown(int rt,int d)

{

    if(lazy[rt])

    {

        sum[rt*]=(sum[rt*]+1ll*lazy[rt]*(d-d/))%mod;

        sum[rt*+]=(sum[rt*+]+1ll*lazy[rt]*(d/))%mod;

        lazy[rt*]=(lazy[rt*]+lazy[rt])%mod;

        lazy[rt*+]=(lazy[rt*+]+lazy[rt])%mod;

        lazy[rt]=;

    }

}

void update(int L,int R,int l,int r,int rt)

{

    if(L<=l&&r<=R){sum[rt]=(sum[rt]+r-l+)%mod,lazy[rt]=(lazy[rt]+)%mod;return;}

    pushdown(rt,r-l+);

    int mid=(l+r)/;

    if(L<=mid)update(L,R,lson);

    if(R>mid)update(L,R,rson);

    sum[rt]=(sum[rt*]+sum[rt*+])%mod;

}

int query(int L,int R,int l,int r,int rt)

{

    if(L<=l&&r<=R)return sum[rt];

    pushdown(rt,r-l+);

    int mid=(l+r)/,ret=;

    if(L<=mid)ret+=query(L,R,lson);

    if(R>mid)ret+=query(L,R,rson);

    return ret%mod;

}

void Update(int x)

{

    while(top[x]!=)update(id[top[x]],id[x],,n,),x=fa[top[x]];

    update(id[],id[x],,n,);

}

int Query(int x)

{

    int ret=;

    while(top[x]!=)ret=(ret+query(id[top[x]],id[x],,n,))%mod,x=fa[top[x]];

    ret+=query(id[],id[x],,n,);

    return ret%mod;

}

int main()

{

    scanf("%d%d",&n,&q);

    for(int i=,x;i<=n;i++)scanf("%d",&x),G[x+].push_back(i);

    dfs(),dfs2(,);

    for(int i=,l,r,z;i<=q;i++)

    scanf("%d%d%d",&l,&r,&z),S[l].push_back((node){i,-,z+}),S[r+].push_back((node){i,,z+});

    for(int i=;i<=n;i++)

    {

        Update(i);

        node x;

        for(int j=;j<S[i].size();j++)x=S[i][j],ans[x.id]=(ans[x.id]+x.v*Query(x.z)+mod)%mod;

    }

    for(int i=;i<=q;i++)printf("%d\n",ans[i]);

}

巴特西

[LNOI2014]LCA（树链剖分+线段树）

最新文章

热门文章