【BZOJ-3626】LCA 树链剖分

3626: [LNOI2014]LCA

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1428 Solved: 526
[Submit][Status][Discuss]

Description

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。
（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）

Input

第一行2个整数n q。
接下来n-1行，分别表示点1到点n-1的父节点编号。
接下来q行，每行3个整数l r z。

Output

输出q行，每行表示一个询问的答案。每个答案对201314取模输出

Sample Input

5 2
0
0
1
1
1 4 3
1 4 2

Sample Output

8
5

HINT

共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。

Source

数据已加强 by saffah

Solution

先是两篇高端的题解：HZW学长 TimeMachine学长

什么LCA，都是骗人的

直接暴力去做，很显然不可以，那么这必然会有一些性质或者转化使之简便

那么考虑一种其他的做法

离线处理，把每个询问拆成两个部分，分别是【1～l-1】和【1～r】那么前缀和？

那么维护一下信息，即z点到根的路径

然后加每个点的时候是把从这个点到根的路径的点权全部+1，然后查询就是查询某个点到根的路径的点权和

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define mod 201314

#define maxn 100100

#define maxq 100100

struct Edgenode{int to,next;}edge[maxn];

int head[maxn],cnt;int n,q,zz;

void add(int u,int v)

{cnt++;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;}

//

int size[maxn],pre[maxn],deep[maxn],son[maxn],fa[maxn],pl[maxn],sz,pr[maxn],top[maxn];

void dfs_1(int x)

{

    size[x]=;

    for(int i=head[x];i;i=edge[i].next)

        if (edge[i].to!=fa[x])

            {

                deep[edge[i].to]=deep[x]+;

                fa[edge[i].to]=x;

                dfs_1(edge[i].to);

                size[x]+=size[edge[i].to];

            }

}

void dfs_2(int x,int chain)

{

    top[x]=chain; pl[x]=++sz;

    int k=n;

    for(int i=head[x];i;i=edge[i].next)

        if(edge[i].to!=fa[x]&&size[edge[i].to]>size[k])

            k=edge[i].to;

    if(k!=n) dfs_2(k,chain);

    for(int i=head[x];i;i=edge[i].next)

        if(edge[i].to!=fa[x]&&edge[i].to!=k)

            dfs_2(edge[i].to,edge[i].to);

}

//

struct Treenode{int l,r,tag,da;}tree[maxn<<];

inline void update(int now)

{tree[now].da=tree[now<<].da+tree[now<<|].da;}

inline void pushdown(int now)

{

    int l=tree[now].l,r=tree[now].r,tag=tree[now].tag;

    int mid=(l+r)>>,ln=mid-l+,rn=r-mid;

    if (tag)

        {

            tree[now].tag=;

            tree[now<<].tag+=tag; tree[now<<|].tag+=tag;

            tree[now<<].da+=ln*tag; tree[now<<|].da+=rn*tag;

        }

}

void build(int now,int l,int r)

{

    tree[now].tag=tree[now].da=;

    tree[now].l=l;tree[now].r=r;

    if (l==r) return;

    int mid=(l+r)>>;

    build(now<<,l,mid); build(now<<|,mid+,r);

}

void segment_change(int now,int L,int R)

{

    pushdown(now);

    if (L<=tree[now].l && R>=tree[now].r)

        {tree[now].da+=(tree[now].r-tree[now].l+);tree[now].tag++;return;}

    int mid=(tree[now].l+tree[now].r)>>;

    if (L<=mid) segment_change(now<<,L,R);

    if (R>mid) segment_change(now<<|,L,R);

    update(now);

}

int segment_ask(int now,int L,int R)

{

    pushdown(now);

    if (L<=tree[now].l && R>=tree[now].r) return tree[now].da;

    int mid=(tree[now].l+tree[now].r)>>; int ans=;

    if (L<=mid) ans+=segment_ask(now<<,L,R);

    if (R>mid) ans+=segment_ask(now<<|,L,R);

    return ans;

}

//

void change(int x,int y)

{

    while (top[x]!=top[y])

        {

            segment_change(,pl[top[x]],pl[x]);

            x=fa[top[x]];

        }

    segment_change(,pl[y],pl[x]);

}

int query(int x,int y)

{

    int ans=;

    while (top[x]!=top[y])

        {

            ans=(ans+segment_ask(,pl[top[x]],pl[x]))%mod;

            x=fa[top[x]];

        }

    ans=(ans+segment_ask(,pl[y],pl[x]))%mod;

    return ans;

}

//

struct Asknode{int z,ans1,ans2;}ask[maxq];

struct Reqnode

{

    int p,id;bool f;

    bool operator < (const Reqnode & A) const

        {return p<A.p;}

}req[maxq<<];

int main()

{

//    freopen("3626.in","r",stdin);

//    freopen("3626.out","w",stdout);

    n=read(),q=read();

    for (int x,i=; i<=n-; i++)

        x=read(),add(x,i);

    for (int a,b,c,i=; i<=q; i++)

        {

            a=read(),b=read(),c=read();

            ask[i].z=c;

            zz++;req[zz].p=a-;req[zz].id=i;req[zz].f=;

            zz++;req[zz].p=b;req[zz].id=i;req[zz].f=;

        }

    sort(req+,req+zz+);

//    for (int i=1; i<=zz; i++)

//        printf("%d %d %d\n",req[i].p,req[i].id,req[i].f);

    build(,,n); dfs_1(); dfs_2(,);

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

//        printf("%d %d %d %d %d %d\n",i,fa[i],deep[i],pl[i],size[i],top[i]);

    int now=-;

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

        {

            while (now<req[i].p)

                now++,change(now,);

//            printf("%d\n",query(ask[req[i].id].z,0));

            if (!req[i].f) ask[req[i].id].ans1=query(ask[req[i].id].z,);

            else ask[req[i].id].ans2=query(ask[req[i].id].z,);

        }

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

        printf("%d\n",(ask[i].ans2-ask[i].ans1+mod)%mod);

    return ;

}

sb错误毁一生！！！！

数据生成器：

#include<cstdio>

#include<ctime>

#include<cstdlib>

using namespace std;

int main()

{

    freopen("3626.in","w",stdout);

    int n;

    srand(time());

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

    n=;

    printf("%d %d\n",n,n);

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

        printf("%d\n",rand()%(i+));

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

        printf("%d %d %d\n",rand()%n,rand()%n,rand()%n);

    return ;

}

巴特西