3626: [LNOI2014]LCA
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2050 Solved: 817
[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
0
0
1
1
1 4 3
1 4 2
Sample Output
5
HINT
共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。
Source
orz gconeice
显然，暴力求解的复杂度是无法承受的。
考虑这样的一种暴力，我们把 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)，均可以完成任务。至此，题目已经被我们完美解决。
z的LCA只能在z到根的路径上，统计到根的路径上每个点被作为LCA几次
很巧妙的转换，[l,r]所有点到根路径+1，然后询问z到根路径权值
显然树链剖分
多组询问，考虑将询问差分，[1, r] − [1, l − 1]，然后离线询问的两个端点，每加到一个now将l-1或者r是now到询问都问一下
//
// main.cpp
// bzoj4196
//
// Created by Candy on 2017/1/2.
// Copyright © 2017年 Candy. All rights reserved.
// #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define lc o<<1
#define rc o<<1|1
#define m ((l+r)>>1)
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
const int N=1e5+,MOD=;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,Q,u,l,r;
char s[];
struct ques{
int z,al,ar;
}q[N];
struct que{
int x,id,isl;
bool operator <(const que &r)const{return x<r.x;}
}a[N];
int p;
struct edge{
int v,ne,c,f;
}e[N<<];
int cnt,h[N];
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
} int deep[N],fa[N],tid[N],tot,top[N],mx[N],size[N];
void dfs(int u){
size[u]=;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(v==fa[u]) continue;
fa[v]=u;deep[v]=deep[u]+;
dfs(v);
size[u]+=size[v];
if(size[v]>size[mx[u]]) mx[u]=v;
}
}
void dfs(int u,int anc){
if(!u) return;
tid[u]=++tot;
top[u]=anc;
dfs(mx[u],anc);
for(int i=h[u];i;i=e[i].ne)
if(e[i].v!=mx[u]&&e[i].v!=fa[u]) dfs(e[i].v,e[i].v);
} struct node{
int sum,add;
}t[N<<];
inline void merge(int o){
t[o].sum=t[lc].sum+t[rc].sum;
}
inline void paint(int o,int l,int r,int d){
t[o].sum+=d*(r-l+);
t[o].add+=d;
}
inline void pushDown(int o,int l,int r){
if(t[o].add){
paint(lson,t[o].add);
paint(rson,t[o].add);
t[o].add=;
}
}
inline void segAdd(int o,int l,int r,int ql,int qr,int d){//printf("add %d %d %d\n",o,l,r);
if(ql<=l&&r<=qr) paint(o,l,r,d);
else{
pushDown(o,l,r);
if(ql<=m) segAdd(lson,ql,qr,d);
if(m<qr) segAdd(rson,ql,qr,d);
merge(o);
}
}
inline int segQue(int o,int l,int r,int ql,int qr){//printf("que %d %d %d %d %d\n",o,l,r,ql,qr);
if(ql<=l&&r<=qr) return t[o].sum;
else{
pushDown(o,l,r);
int ans=;
if(ql<=m) ans+=segQue(lson,ql,qr);
if(m<qr) ans+=segQue(rson,ql,qr);
return ans;
}
}
void build(int o,int l,int r){
if(l==r) paint(o,l,r,);
else{
build(lson);
build(rson);
}
} void add(int x,int y,int d){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
segAdd(,,n,tid[top[x]],tid[x],d);
x=fa[top[x]];
}
if(tid[x]>tid[y]) swap(x,y);
segAdd(,,n,tid[x],tid[y],d);
}
int query(int x,int y){
int ans=;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=segQue(,,n,tid[top[x]],tid[x]);ans%=MOD;
x=fa[top[x]];
}
if(tid[x]>tid[y]) swap(x,y);
ans+=segQue(,,n,tid[x],tid[y]);ans%=MOD;
return ans;
}
int main(){
n=read();Q=read();
for(int i=;i<=n;i++) u=read()+,ins(u,i);
dfs();dfs(,);
build(,,n);
for(int i=;i<=Q;i++){
l=read();r=read()+;q[i].z=read()+;
a[++p].x=l;a[p].id=i;a[p].isl=;
a[++p].x=r;a[p].id=i;a[p].isl=;
}
sort(a+,a++p);
int now=;
for(int i=;i<=p;i++){//printf("a %d %d %d\n",a[i].x,a[i].id,a[i].isl);
while(now<=a[i].x) add(,now,),now++;
int _=a[i].id;
if(a[i].isl) q[_].al=query(,q[_].z);
else q[_].ar=query(,q[_].z);
}
for(int i=;i<=Q;i++) printf("%d\n",(q[i].ar-q[i].al+MOD)%MOD);
}
在线的话可以用主席树，在dfs序上建主席树
这样每个线段树与历史版本的差距是一个节点，也就是一个点到根的路径，有logn段，每段有logn个新开节点，复杂度log^2n
好麻烦还要带标记啊
[2017-01-04 00:01:51]
我太弱了，不是M就是R，不玩了