BZOJ_3626_[LNOI2014]LCA_离线+树剖

118 阅读 0 评论 78 点赞

我是靠谱客的博主喜悦大山，这篇文章主要介绍BZOJ_3626_[LNOI2014]LCA_离线+树剖，现在分享给大家，希望可以做个参考。

题意：

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

分析：

求$sumlimits_{lle ile r}dep(LCA(i,z))$相当于把[l,r]区间内所有点依次插入。

每次把点到1路径上所有点+1，可以发现z到1路径上的点权和即为所求。

并且该操作具有区间可减性。那么我们把所有询问拆成[0~l-1],[0~r]两部分。

排个序离线计算。

代码：

复制代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
#define LL long long
#define ls p<<1
#define rs p<<1|1
int head[N],to[N<<1],nxt[N<<1],cnt,n,m,r,mod=201314;
int t[N<<2],lz[N<<2],tot;
int siz[N],top[N],son[N],fa[N],dep[N],idx[N];
LL now,ans[N];
struct A{
int pos,z,flg,id;
}a[N];
bool cmp(const A &x,const A &y){
return x.pos<y.pos;
}
inline void add(int u,int v){
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs1(int x,int y){
fa[x]=y;dep[x]=dep[y]+1;siz[x]=1;
for(int i=head[x];i;i=nxt[i]){
if(to[i]!=y){
dfs1(to[i],x);
siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]])son[x]=to[i];
}
}
}
void dfs2(int x,int t){
top[x]=t;idx[x]=++tot;
if(son[x])dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i]){
if(to[i]!=fa[x]&&to[i]!=son[x])dfs2(to[i],to[i]);
}
}
void pud(int l,int r,int p){
if(!lz[p])return ;
int mid=l+r>>1;
lz[ls]=(lz[ls]+lz[p])%mod;
lz[rs]=(lz[rs]+lz[p])%mod;
t[ls]=(t[ls]+lz[p]*(mid-l+1))%mod;
t[rs]=(t[rs]+lz[p]*(r-mid))%mod;
lz[p]=0;
}
void up(int l,int r,int x,int y,int c,int p){
if(x<=l&&r<=y){
lz[p]=(lz[p]+c)%mod;
t[p]=(t[p]+c*(r-l+1))%mod;return ;
}
pud(l,r,p);
int mid=l+r>>1;
if(x<=mid)up(l,mid,x,y,c,ls);
if(y>mid)up(mid+1,r,x,y,c,rs);
t[p]=(t[ls]+t[rs])%mod;
}
int query(int l,int r,int x,int y,int p){
if(x<=l&&r<=y){
return t[p];
}
pud(l,r,p);
int mid=l+r>>1;
int re=0;
if(x<=mid)re=(re+query(l,mid,x,y,ls))%mod;
if(y>mid)re=(re+query(mid+1,r,x,y,rs))%mod;
return re;
}
void insert(int x){
int y=1;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])swap(x,y);
up(1,n,idx[top[y]],idx[y],1,1);
y=fa[top[y]];
}if(dep[x]<dep[y])swap(x,y);
up(1,n,idx[y],idx[x],1,1);
}
LL ask(int x){
LL re=0;
int y=1;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])swap(x,y);
re+=query(1,n,idx[top[y]],idx[y],1);
re%=mod;
y=fa[top[y]];
}if(dep[x]<dep[y])swap(x,y);
re+=query(1,n,idx[y],idx[x],1);
re%=mod;
return re;
}
int main(){
scanf("%d%d",&n,&m);
int x;
for(int i=2;i<=n;i++){
scanf("%d",&x);x++;
add(x,i);add(i,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].pos,&a[i+m].pos,&a[i].z);
a[i+m].pos++;a[i].z++;
a[i+m].z=a[i].z;a[i].id=a[i+m].id=i;a[i+m].flg=1;
}
sort(a+1,a+m+m+1,cmp);
int dir=0;
for(int i=1;i<=m+m;i++){
if(dir==a[i].pos){
ans[a[i].id+a[i].flg*m]=ask(a[i].z);continue;
}else{
for(int j=dir+1;j<=a[i].pos;j++){
insert(j);
}
ans[a[i].id+a[i].flg*m]=ask(a[i].z);dir=a[i].pos;
}
}
for(int i=1;i<=m;i++){
printf("%lldn",(ans[i+m]-ans[i]+mod)%mod);
}
}
/*
5 2
0
0
1
1
1 4 3
1 4 2
*/

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
#define LL long long
#define ls p<<1
#define rs p<<1|1
int head[N],to[N<<1],nxt[N<<1],cnt,n,m,r,mod=201314;
int t[N<<2],lz[N<<2],tot;
int siz[N],top[N],son[N],fa[N],dep[N],idx[N];
LL now,ans[N];
struct A{
int pos,z,flg,id;
}a[N];
bool cmp(const A &x,const A &y){
return x.pos<y.pos;
}
inline void add(int u,int v){
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs1(int x,int y){
fa[x]=y;dep[x]=dep[y]+1;siz[x]=1;
for(int i=head[x];i;i=nxt[i]){
if(to[i]!=y){
dfs1(to[i],x);
siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]])son[x]=to[i];
}
}
}
void dfs2(int x,int t){
top[x]=t;idx[x]=++tot;
if(son[x])dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i]){
if(to[i]!=fa[x]&&to[i]!=son[x])dfs2(to[i],to[i]);
}
}
void pud(int l,int r,int p){
if(!lz[p])return ;
int mid=l+r>>1;
lz[ls]=(lz[ls]+lz[p])%mod;
lz[rs]=(lz[rs]+lz[p])%mod;
t[ls]=(t[ls]+lz[p]*(mid-l+1))%mod;
t[rs]=(t[rs]+lz[p]*(r-mid))%mod;
lz[p]=0;
}
void up(int l,int r,int x,int y,int c,int p){
if(x<=l&&r<=y){
lz[p]=(lz[p]+c)%mod;
t[p]=(t[p]+c*(r-l+1))%mod;return ;
}
pud(l,r,p);
int mid=l+r>>1;
if(x<=mid)up(l,mid,x,y,c,ls);
if(y>mid)up(mid+1,r,x,y,c,rs);
t[p]=(t[ls]+t[rs])%mod;
}
int query(int l,int r,int x,int y,int p){
if(x<=l&&r<=y){
return t[p];
}
pud(l,r,p);
int mid=l+r>>1;
int re=0;
if(x<=mid)re=(re+query(l,mid,x,y,ls))%mod;
if(y>mid)re=(re+query(mid+1,r,x,y,rs))%mod;
return re;
}
void insert(int x){
int y=1;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])swap(x,y);
up(1,n,idx[top[y]],idx[y],1,1);
y=fa[top[y]];
}if(dep[x]<dep[y])swap(x,y);
up(1,n,idx[y],idx[x],1,1);
}
LL ask(int x){
LL re=0;
int y=1;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])swap(x,y);
re+=query(1,n,idx[top[y]],idx[y],1);
re%=mod;
y=fa[top[y]];
}if(dep[x]<dep[y])swap(x,y);
re+=query(1,n,idx[y],idx[x],1);
re%=mod;
return re;
}
int main(){
scanf("%d%d",&n,&m);
int x;
for(int i=2;i<=n;i++){
scanf("%d",&x);x++;
add(x,i);add(i,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].pos,&a[i+m].pos,&a[i].z);
a[i+m].pos++;a[i].z++;
a[i+m].z=a[i].z;a[i].id=a[i+m].id=i;a[i+m].flg=1;
}
sort(a+1,a+m+m+1,cmp);
int dir=0;
for(int i=1;i<=m+m;i++){
if(dir==a[i].pos){
ans[a[i].id+a[i].flg*m]=ask(a[i].z);continue;
}else{
for(int j=dir+1;j<=a[i].pos;j++){
insert(j);
}
ans[a[i].id+a[i].flg*m]=ask(a[i].z);dir=a[i].pos;
}
}
for(int i=1;i<=m;i++){
printf("%lldn",(ans[i+m]-ans[i]+mod)%mod);
}
}
/*
5 2
0
0
1
1
1 4 3
1 4 2
*/