BZOJ 3626 【树链剖分/离线处理/差分】

LNOI2014 LCA

[Description]

给出一个以0结点为根的n个结点的树,节点编号0~n-1。
设$f(u)$为结点$u$的深度,$lca(u,v)$为结点u,v的最近公共祖先。
给出q个询问(l,r,z),要求每个询问输出: $\sum_{i=l}^rf(lca(i,z))$

[Hint]

$n,q≤5\cdot 10^4$

[Solution]

我们着重讨论思考过程。
纯暴力复杂度$O(q\cdot n\cdot logn)$,显然爆炸。
考虑模型转化。在计算某个询问的时候,我们可以将结点z到根路径上的所有点的点权设为1,答案即为结点[l,r]到根路径上的点权和,而这个操作又符合对称性和叠加性,即你可以将结点[l,r]到根路径上所有点的点权+1来计算z到根的路径上的点权和。所以想到了什么?树剖!
进一步思考,区间查询[l,r]并没有什么可循的规律,所以考虑是否可以查分查询。
当然是可以的,对于某个询问,我们先将1~l-1的点加进去,算出z的查询值,再将l~r的点加进去,再算出z的查询值减去之前的就是答案了。这个操作,对于所有询问都可以同时做,所以就可以离线处理了。
最后的复杂度为$O((q+n)\cdot logn)$
每一步都精妙无比,好题~

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define pb push_back
#define ST SegmentTree
#define TCS TreeChainSubdivision
using namespace std;

typedef long long ll;

inline int read(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}

const int mod=201314;
const int maxn=5e4+1;
int res[maxn];
int L[maxn],R[maxn],Z[maxn];
vector<int> LL[maxn],RR[maxn];

int to[maxn],nxt[maxn],cur[maxn],fa[maxn],cnt;
void insert(int u,int v){
to[cnt]=v,nxt[cnt]=cur[u],cur[u]=cnt++,fa[v]=u;
}

struct TCS{
struct ST{
static const int logn=17;
int log,sum[1<<logn],flag[1<<logn];
void init(int n){
log=1; while(n) log<<=1,n>>=1;
}
void maintain(int l,int r,int o){
int lc=o*2+1,rc=o*2+2;
sum[o]=0;
if(l<r) sum[o]=(sum[lc]+sum[rc])%mod;
sum[o]=(sum[o]+(ll)(r-l+1)*flag[o])%mod;
}
void add(int l,int r,int L,int R,int o){
if(l<=L && R<=r) flag[o]++;
else{
int M=(L+R)/2;
if(l<=M) add(l,r,L,M,o*2+1);
if(M<r) add(l,r,M+1,R,o*2+2);
}
maintain(L,R,o);
}
int query(int l,int r,int L,int R,int add,int o){
if(l<=L && R<=r) return (sum[o]+(ll)(R-L+1)*add)%mod;
else{
int res=0,M=(L+R)/2;
if(l<=M) res=(res+query(l,r,L,M,add+flag[o],o*2+1))%mod;
if(M<r) res=(res+query(l,r,M+1,R,add+flag[o],o*2+2))%mod;
return res;
}
}
}st;

int hson[maxn],d[maxn],size[maxn];
void dfs1(int u,int dep){
d[u]=dep,size[u]=1;
for(int i=cur[u];i>=0;i=nxt[i]){
int v=to[i];
dfs1(v,dep+1);
size[u]+=size[v];
if(size[v]>size[hson[u]]) hson[u]=v;
}
}
int top[maxn],id[maxn],cnt;
void dfs2(int u,int tp){
top[u]=tp,id[u]=++cnt;
if(hson[u]) dfs2(hson[u],tp);
for(int i=cur[u];i>=0;i=nxt[i]){
int v=to[i];
if(v!=hson[u]) dfs2(v,v);
}
}
void init(int n){
st.init(n);
dfs1(1,1); dfs2(1,1);
}

void add(int u,int v){
int tpu=top[u],tpv=top[v];
while(tpu!=tpv){
if(d[tpu]<d[tpv]){
swap(u,v); swap(tpu,tpv);
}
st.add(id[tpu],id[u],1,st.log,0);
u=fa[tpu],tpu=top[u];
}
if(u==v){ st.add(id[u],id[u],1,st.log,0); return; }
if(d[u]<d[v]) swap(u,v);
st.add(id[v],id[u],1,st.log,0);
}
int query(int u,int v){
int res=0,tpu=top[u],tpv=top[v];
while(tpu!=tpv){
if(d[tpu]<d[tpv]){
swap(u,v); swap(tpu,tpv);
}
res=(res+st.query(id[tpu],id[u],1,st.log,0,0))%mod;
u=fa[tpu],tpu=top[u];
}
if(u==v) return res+st.query(id[u],id[u],1,st.log,0,0);
if(d[u]<d[v]) swap(u,v);
res=(res+st.query(id[v],id[u],1,st.log,0,0))%mod;
return res;
}
}tcs;

int main(){
memset(cur,-1,sizeof(cur));
int n=read(),m=read();
for(int i=2;i<=n;i++) insert(read()+1,i);
for(int i=0;i<m;i++){
L[i]=read(),R[i]=read()+1,Z[i]=read()+1;
LL[L[i]].pb(i),RR[R[i]].pb(i);
}

tcs.init(n);
for(int i=1,sum=n<<1;i<=n && sum;i++){
tcs.add(1,i);
for(int j=0,lim=LL[i].size();j<lim;j++,sum--)
res[LL[i][j]]=-tcs.query(1,Z[LL[i][j]]);
for(int j=0,lim=RR[i].size();j<lim;j++,sum--)
res[RR[i][j]]+=tcs.query(1,Z[RR[i][j]]);
}

for(int i=0;i<m;i++)
printf("%d\n",(res[i]+mod)%mod);

return 0;
}