ZJOI2017 day2 T2 线段树想法题

考完D2发现自己简直zz了。。。花式扔基本分

首先这道题有个显然的套路：树上一些点到一个定点的距离和=这些点深度和+点数*定点深度和-2*lca深度和

——上一次见这个套路是LNOI2014，上次做的时候还比较naive：http://www.cnblogs.com/wanglichao/p/6425893.html

这次考场上也只想到这一步了，，并没有发现广义线段树的奇特性质

奇特性质：被选中的从左到右一定是一串右儿子和一串左儿子，而且都是挂在l-1到r+1上的连续右（左）儿子

这么一来，一个询问可以分成两部分，这两部分都可以O(n)预处理出来

在预处理的时候考虑维护两个东西：从根节点到当前点的链上所直接挂的所有右儿子的个数（记为sum[i]）和深度和（sumd[i]）

那么在统计的时候这些点深度和+点数*定点深度和-2*lca深度和可以轻松算出

（一脸懵逼.jpg）

Q:如何算lca深度和？

A:分类讨论，计算询问的定点挂到链上是哪里（以下称为悬挂点x）

①悬挂点以上的点与定点的lca深度为自己深度-1，所以总和为“sumd[x]-sum[x]”

②悬挂点的右儿子如果被算在答案里，那么深度就是"dep[x]+1"

③悬挂点以下的点与定点的lca深度一定为dep[x]，总和为"(sum[l-1]-sum[x])*dep[x]"

求和即可（注意细节）

左儿子同理

Q:l=1或者r=n怎么办

A:只算半边（自行理解，不可言传）

上个代码冷静一下（目前uoj上最短榜第一来自这个代码微改@wzf2000）：

 #include <bits/stdc++.h>

 #define bel(x,y) (L[x]>=L[y] && R[x]<=R[y])

 using namespace std;

 long long n,N,IN,m,u,l,r,LOG;

 long long mer[],ls[],rs[],sum[][],dep[],sd[][];

 long long fa[][];

 long long L[],R[],nod[];

 long long lca(long long a,long long b)

 {

     if(bel(a,b)) return b;

     if(bel(b,a)) return a;

     long long now=a;

     for(long long i=LOG;i>=;i--)

     if(fa[now][i] && !bel(b,fa[now][i])) now=fa[now][i];

     return fa[now][];

 }

 void Dfs(long long now)

 {

     if(!ls[now]) return;

     sum[rs[now]][]=sum[now][];

     sum[rs[now]][]=sum[now][]+;

     sum[ls[now]][]=sum[now][]+;

     sum[ls[now]][]=sum[now][];

     dep[ls[now]]=dep[now]+;

     dep[rs[now]]=dep[now]+;

     sd[rs[now]][]=sd[now][];

     sd[rs[now]][]=sd[now][]+dep[now]+;

     sd[ls[now]][]=sd[now][]+dep[now]+;

     sd[ls[now]][]=sd[now][];

     Dfs(ls[now]);

     Dfs(rs[now]);

 }

 long long dfs(long long l,long long r)

 {

     long long now=++N;

     L[now]=l;R[now]=r;

     for(long long i=;fa[fa[now][i]][i];i++) fa[now][i+]=fa[fa[now][i]][i];

     if(l==r) return nod[l]=now;

     long long me=mer[IN++];

     fa[N+][]=now;

     ls[now]=dfs(l,me);

     fa[N+][]=now;

     rs[now]=dfs(me+,r);

     return now;

 }

 long long getl(long long l)

 {

     long long lc=lca(l,u);

     long long now=dep[lc]*(sum[l][]-sum[lc][])+(bel(l,ls[lc]) && lc!=u)+sd[lc][]-sum[lc][];

     long long ans=sd[l][]+sum[l][]*dep[u]-now*;

     return ans;

 }

 long long getr(long long r)

 {

     long long lc=lca(r,u);

     long long now=dep[lc]*(sum[r][]-sum[lc][])+(bel(r,rs[lc]) && lc!=u)+sd[lc][]-sum[lc][];

     long long ans=sd[r][]+sum[r][]*dep[u]-now*;

     return ans;

 }

 int main()

 {

     scanf("%d",&n);

     for(long long i=;i<=n;i<<=)

         LOG++;

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

         scanf("%d",&mer[i]);

     IN=;

     dfs(,n);

     Dfs();

     scanf("%d",&m);

     for(long long i=;i<=m;i++)

     {

         scanf("%d%d%d",&u,&l,&r);

         --l;++r;

         if(!l && r>n)

         {

             printf("%d\n",dep[u]);

             continue;

         }

         long long ans=;

         if(l)

             ans+=getl(nod[l])-((r<=n)?getl(ls[lca(nod[l],nod[r])]):);

         if(r<=n)

             ans+=getr(nod[r])-(l?getr(rs[lca(nod[l],nod[r])]):);

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

ZJOI2017 day2 T2 线段树想法题

最新文章

热门文章

巴特西

ZJOI2017 day2 T2 线段树 想法题

最新文章

热门文章

ZJOI2017 day2 T2 线段树想法题