正解:树剖+线段树

解题报告:

看到$dep[lca]$啥的就想到之前托腮腮$CSP$模拟$D1T3$的那个套路,,,

然后试下这个想法,于是$dep[lca(x,y)]=\sum_{i=1}^{\infty}[i\leq dep[lca(x,y)]]$,就可以是,从$x$到根全部加一然后查询$y$到根的权值和.

现在变成$\sum_{i=l}^r dep[lca(i,x)]$,那就$l$到$r$到根全加一然后查询$x$到根的权值和.

显然考虑差分呗?就$1$到$r$全加一的权值和减去$1$到$l-1$全加一的权值和.

于是就从$1$枚举到$n$每次从当前节点到根全加一,顺便维护下这个答案就完事$QwQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define lowbit(x) (x&(-x))

#define rg register

#define gc getchar()

#define ls(x) (x<<1)

#define rs(x) ((x<<1)|1)

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];~i;i=edge[i].nxt)

const int N=+,mod=;

int n,q,dfn[N],sz[N],top[N],fa[N],as[N],hs[N],dfn_cnt,tr[N<<],ad[N<<];

vector<int>son[N];

struct node{int id,x,op;};

vector<node>V[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void add(ri &x,ri y){x+=y;if(x>=mod)x-=mod;if(x<)x+=mod;}

il void dfs1(ri x)

{

    sz[x]=;ri siz=son[x].size();

    rp(i,,siz-){dfs1(son[x][i]),sz[x]+=sz[son[x][i]];if(sz[son[x][i]]>sz[hs[x]])hs[x]=son[x][i];}

}

il void dfs2(ri x,ri tp)

{

    top[x]=tp;dfn[x]=++dfn_cnt;if(hs[x])dfs2(hs[x],tp);ri siz=son[x].size();

    rp(i,,siz-)if(son[x][i]^hs[x])dfs2(son[x][i],son[x][i]);

}

il void pushdown(ri x,ri l,ri r)

{

    if(!ad[x])return;

    ri mid=(l+r)>>;

    add(tr[ls(x)],1ll*ad[x]*(mid-l+)%mod),add(tr[rs(x)],1ll*ad[x]*(r-mid)%mod);

    ad[ls(x)]+=ad[x],ad[rs(x)]+=ad[x];ad[x]=;

}

void modify(ri x,ri l,ri r,ri to_l,ri to_r)

{

    if(to_l<=l && r<=to_r){add(tr[x],r-l+);add(ad[x],);return;}

    pushdown(x,l,r);

    ri mid=(l+r)>>;if(mid>=to_l)modify(ls(x),l,mid,to_l,to_r);if(mid<to_r)modify(rs(x),mid+,r,to_l,to_r);

    tr[x]=(tr[ls(x)]+tr[rs(x)])%mod;

}

int query(ri x,ri l,ri r,ri to_l,ri to_r)

{

    if(to_l<=l && r<=to_r)return tr[x];

    pushdown(x,l,r);ri mid=(l+r)>>,ret=;

    if(mid>=to_l)ret=query(ls(x),l,mid,to_l,to_r);;if(mid<to_r)add(ret,query(rs(x),mid+,r,to_l,to_r));

    return ret;

}

int main()

{

    freopen("4211.in","r",stdin);freopen("4211.out","w",stdout);

    n=read();q=read();rp(i,,n)son[fa[i]=read()+].push_back(i);dfs1();dfs2(,);

    rp(i,,q){ri l=read(),r=read()+,x=read()+;V[l].push_back((node){i,x,-});V[r].push_back((node){i,x,});}

    rp(i,,n)

    {

        ri nw=i;while(nw)modify(,,n,dfn[top[nw]],dfn[nw]),nw=fa[top[nw]];

        for(auto j:V[i])

        {nw=j.x;while(nw)add(as[j.id],j.op*query(,,n,dfn[top[nw]],dfn[nw])),nw=fa[top[nw]];}

    }

    rp(i,,q)printf("%d\n",as[i]);

    return ;

}

巴特西

洛谷$P4211\ [LNOI2014]\ LCA$ 树链剖分+线段树

正解:树剖+线段树

解题报告:

最新文章

热门文章