BZOJ3626 LCA

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

正解：树链剖分+线段树

解题报告：

　　我这种蒟蒻一看到题目第一反应就是打暴力，真是没戏了。

　　想了20分钟没想出来就弃疗了，直接看了hzwer神犇的题解，%%%hzwer：http://hzwer.com/3891.html

　　其实我只看了一眼那个结论我马上就会打了，瞬间变水题。关键是操作具有很多奇奇怪怪的性质，而且转化成求路径上的点权和。

　　正版推导：

　　考虑这样的一种暴力，我们把 z 到根上的点全部打标记，对于 l 到 r 之间的点，向上搜索到第一个有标记的点求出它的深度统计答案。观察到，深度其实就是上面有几个已标记了的点（包括自身）。所以，我们不妨把 z 到根的路径上的点全部 +1，对于 l 到 r 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现，实际上这个操作具有叠加性，且可逆。也就是说我们可以对于 l 到 r 之间的点 i，将 i 到根的路径上的点全部 +1, 转而询问 z 到根的路径上的点（包括自身）的权值和就是这个询问的答案。把询问差分下，也就是用 [1, r] − [1, l − 1] 来计算答案，那么现在我们就有一个明显的解法。从 0 到 n − 1 依次插入点 i，即将 i 到根的路径上的点全部+1。离线询问答案即可。我们现在需要一个数据结构来维护路径加和路径求和，显然树链剖分或LCT 均可以完成这个任务。树链剖分的复杂度为 O((n + q)· log n · log n)，LCT的复杂度为 O((n + q)· log n)，均可以完成任务。至此，题目已经被我们完美解决。

 //It is made by jump~

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 const int MOD = ;

 const int MAXQ = ;

 int n,q,ecnt;

 int first[MAXN],next[MAXN*],to[MAXN*];

 int father[MAXN],top[MAXN],son[MAXN],size[MAXN],deep[MAXN],id[MAXN],pre[MAXN];

 int ql,qr,daan;

 struct wen{

     int pos,z,id,ans;

 }a[MAXQ];

 struct node{

     int sum,lazy,l,r,size;

 }jump[MAXN*];

 inline int getint()

 {

     int w=,q=;

     char c=getchar();

     while((c<'' || c>'') && c!='-') c=getchar();

     if (c=='-')  q=, c=getchar();

     while (c>='' && c<='') w=w*+c-'', c=getchar();

     return q ? -w : w;

 }

 inline void dfs(int x,int fa){

     size[x]=;

     for(int i=first[x];i;i=next[i]) {

     int v=to[i]; deep[v]=deep[x]+;

     dfs(v,x);

     size[x]+=size[v];

     if(size[v]>size[son[x]]) son[x]=v;

     }

 }

 inline void dfs2(int x,int fa){

     id[x]=++ecnt; pre[ecnt]=x;

     if(son[x]) top[son[x]]=top[x],dfs2(son[x],x);

     for(int i=first[x];i;i=next[i]) {

     int v=to[i];

     if(v!=son[x]) {

         top[v]=v;

         dfs2(v,x);

     }

     }

 }

 inline bool cmp(wen q,wen qq){ return q.pos<qq.pos; }

 inline bool ccmp(wen q,wen qq){ return q.id<qq.id; }

 inline void pushdown(int x){

     if(jump[x].size==) return ;

     if(jump[x].lazy) {

     int lc=x*,rc=lc+;

     jump[lc].lazy+=jump[x].lazy;jump[rc].lazy+=jump[x].lazy;

     jump[lc].sum+=jump[x].lazy*jump[lc].size;jump[rc].sum+=jump[x].lazy*jump[rc].size;

     jump[x].lazy=;

     }

 }

 inline void update(int root,int l,int r){

     pushdown(root);

     if(ql<=l && r<=qr) {

     jump[root].lazy++;

     jump[root].sum+=jump[root].size;

     return ;

     }

     int mid=(l+r)/; int lc=root*,rc=lc+;

     if(ql<=mid) update(lc,l,mid); if(qr>mid) update(rc,mid+,r);

     jump[root].sum=jump[lc].sum+jump[rc].sum;

 }

 inline void query(int root,int l,int r){

     pushdown(root);

     if(ql<=l && r<=qr) {

     daan+=jump[root].sum;

     if(daan>=MOD) daan=daan%MOD;

     return ;

     }

     int mid=(l+r)/; int lc=root*,rc=lc+;

     if(ql<=mid) query(lc,l,mid); if(qr>mid) query(rc,mid+,r);

     jump[root].sum=jump[lc].sum+jump[rc].sum;

 }

 inline void lca(int x){

     int f1=top[x];

     while(x) {

     ql=id[f1],qr=id[x];

     update(,,n);

     x=father[f1]; f1=top[x];

     }

 }

 inline int up(int x){

     int f1=top[x];

     int total=;

     while(x) {

     ql=id[f1]; qr=id[x]; daan=;

     query(,,n);

     total+=daan;

     x=father[f1]; f1=top[x];

     if(total>=MOD) total%=MOD;

     }

     return total;

  }

 inline void build(int root,int l,int r){

     jump[root].l=l; jump[root].r=r; jump[root].size=r-l+;

     if(l==r) return ;

     int mid=(l+r)/; int lc=root*,rc=lc+;

     build(lc,l,mid); build(rc,mid+,r);

 }

 inline void work(){

     n=getint(); q=getint();

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

     father[i+]=getint()+;

     next[++ecnt]=first[father[i+]]; to[ecnt]=i+; first[father[i+]]=ecnt;

     }

     deep[]=; dfs(,); top[]=; ecnt=; dfs2(,);

     int x,y,z;

     ecnt=;

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

     x=getint()+; y=getint()+; z=getint()+;

     a[++ecnt].pos=x-; a[ecnt].id=ecnt; a[ecnt].z=z;

     a[++ecnt].pos=y; a[ecnt].id=ecnt; a[ecnt].z=z;

     }

     sort(a+,a+ecnt+,cmp);

     int now=;

     build(,,n);

     for(int i=;i<=ecnt;i++) {

     while(now<a[i].pos) {

         lca(now+);  now++;

     }

     a[i].ans=up(a[i].z);    if(a[i].ans>MOD) a[i].ans%=MOD;

     }

     sort(a+,a+ecnt+,ccmp);

     for(int i=;i<=ecnt;i+=) printf("%d\n",( (a[i+].ans-a[i].ans)+MOD )%MOD);

 }

 int main()

 {

     work();

     return ;

 }

巴特西