「BZOJ3626」[LNOI2014] LCA

2014年7月28日11,81710

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。

题解

直接引用清华爷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)，均可以完成任务。至此，题目已经被我们完美解决。

非常清楚啊，接下来是吐槽

妈蛋这道题完全没有裸暴力分T T

还有其实这题根本不用会求lca，根本用不到倍增T T

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 201314
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt,place;
int bin[20];
int son[50005],last[50005],fa[50005],belong[50005],pl[50005],deep[50005];
struct edge{int to,next;}e[50005];
struct que{int z,ans1,ans2;}q[50005];
struct data{int num,p;bool flag;}a[100005];
struct seg{int l,r,sum,tag,size;}t[200005];
inline bool operator<(data a,data b)
{
	return a.p<b.p;
}
inline void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void dfs1(int x)
{
	son[x]=1;
	for(int i=last[x];i;i=e[i].next)
	{
		if(e[i].to==fa[x])continue;
		deep[e[i].to]=deep[x]+1;
		fa[e[i].to]=x;
		dfs1(e[i].to);
		son[x]+=son[e[i].to];
	}
}
void dfs2(int x,int chain)
{
	belong[x]=chain;pl[x]=++place;
	int k=n;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x]&&son[e[i].to]>son[k])
			k=e[i].to;
	if(k!=n)dfs2(k,chain);
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x]&&e[i].to!=k)
			dfs2(e[i].to,e[i].to);
}
inline void pushdown(int k)
{
	if(t[k].l==t[k].r||!t[k].tag)return;
	int tag=t[k].tag;t[k].tag=0;
	t[k<<1].sum=t[k<<1].sum+t[k<<1].size*tag;
	t[k<<1|1].sum=t[k<<1|1].sum+t[k<<1|1].size*tag;
	t[k<<1].tag=t[k<<1].tag+tag;
	t[k<<1|1].tag=t[k<<1|1].tag+tag;
}
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;t[k].size=r-l+1;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void update(int k,int x,int y)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==x&&y==r)
	{
		t[k].tag++;t[k].sum+=t[k].size;
		return;
	}
	int mid=(l+r)>>1;
	if(y<=mid)update(k<<1,x,y);
	else if(x>mid)update(k<<1|1,x,y);
	else 
	{
		update(k<<1,x,mid);
		update(k<<1|1,mid+1,y);
	}
	t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
void solve_update(int x,int f)
{
	while(belong[x]!=belong[f])
	{
		update(1,pl[belong[x]],pl[x]);
		x=fa[belong[x]];
	}
	update(1,pl[f],pl[x]);
}
int query(int k,int x,int y)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==x&&y==r)return t[k].sum;
	int mid=(l+r)>>1;
	if(y<=mid)return query(k<<1,x,y);
	else if(x>mid)return query(k<<1|1,x,y);
	else return query(k<<1,x,mid)+query(k<<1|1,mid+1,y);
}
int solve_query(int x,int f)
{
	int sum=0;
	while(belong[x]!=belong[f])
	{
		sum+=query(1,pl[belong[x]],pl[x]);
		sum%=mod;
		x=fa[belong[x]];
	}
	sum+=query(1,pl[f],pl[x]);sum%=mod;
	return sum;
}
int main()
{
	//freopen("lca.in","r",stdin);
	//freopen("lca.out","w",stdout);
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=(bin[i-1]<<1);
    n=read();m=read();
	for(int i=1;i<n;i++)
	{
		int x=read();insert(x,i);
	}
	int tot=0;
	for(int i=1;i<=m;i++)
	{
		int l=read(),r=read();
	    q[i].z=read();
		a[++tot].p=l-1;a[tot].num=i;a[tot].flag=0;
	    a[++tot].p=r;a[tot].num=i;a[tot].flag=1;
	}
	build(1,1,n);
	sort(a+1,a+tot+1);
	dfs1(0);dfs2(0,0);
	int now=-1;
	for(int i=1;i<=tot;i++)
	{
		while(now<a[i].p)
		{
			now++;
			solve_update(now,0);
		}
		int t=a[i].num;
	    if(!a[i].flag)q[t].ans1=solve_query(q[t].z,0);
		else q[t].ans2=solve_query(q[t].z,0);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",(q[i].ans2-q[i].ans1+mod)%mod);
	return 0;
}

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

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 201314

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt,place;

int bin[20];

int son[50005],last[50005],fa[50005],belong[50005],pl[50005],deep[50005];

struct edge{int to,next;}e[50005];

struct que{int z,ans1,ans2;}q[50005];

struct data{int num,p;bool flag;}a[100005];

struct seg{int l,r,sum,tag,size;}t[200005];

inline bool operator<(data a,data b)

{

return a.p<b.p;

}

inline void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

void dfs1(int x)

{

son[x]=1;

for(int i=last[x];i;i=e[i].next)

{

if(e[i].to==fa[x])continue;

deep[e[i].to]=deep[x]+1;

fa[e[i].to]=x;

dfs1(e[i].to);

son[x]+=son[e[i].to];

}

void dfs2(int x,int chain)

{

belong[x]=chain;pl[x]=++place;

int k=n;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x]&&son[e[i].to]>son[k])

k=e[i].to;

if(k!=n)dfs2(k,chain);

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x]&&e[i].to!=k)

dfs2(e[i].to,e[i].to);

}

inline void pushdown(int k)

{

if(t[k].l==t[k].r||!t[k].tag)return;

int tag=t[k].tag;t[k].tag=0;

t[k<<1].sum=t[k<<1].sum+t[k<<1].size*tag;

t[k<<1|1].sum=t[k<<1|1].sum+t[k<<1|1].size*tag;

t[k<<1].tag=t[k<<1].tag+tag;

t[k<<1|1].tag=t[k<<1|1].tag+tag;

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;t[k].size=r-l+1;

if(l==r)return;

int mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

}

void update(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&y==r)

{

t[k].tag++;t[k].sum+=t[k].size;

return;

}

int mid=(l+r)>>1;

if(y<=mid)update(k<<1,x,y);

else if(x>mid)update(k<<1|1,x,y);

else

{

update(k<<1,x,mid);

update(k<<1|1,mid+1,y);

}

t[k].sum=t[k<<1].sum+t[k<<1|1].sum;

}

void solve_update(int x,int f)

{

while(belong[x]!=belong[f])

{

update(1,pl[belong[x]],pl[x]);

x=fa[belong[x]];

}

update(1,pl[f],pl[x]);

}

int query(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&y==r)return t[k].sum;

int mid=(l+r)>>1;

if(y<=mid)return query(k<<1,x,y);

else if(x>mid)return query(k<<1|1,x,y);

else return query(k<<1,x,mid)+query(k<<1|1,mid+1,y);

}

int solve_query(int x,int f)

{

int sum=0;

while(belong[x]!=belong[f])

{

sum+=query(1,pl[belong[x]],pl[x]);

sum%=mod;

x=fa[belong[x]];

}

sum+=query(1,pl[f],pl[x]);sum%=mod;

return sum;

}

int main()

{

//freopen("lca.in","r",stdin);

//freopen("lca.out","w",stdout);

bin[0]=1;for(int i=1;i<20;i++)bin[i]=(bin[i-1]<<1);

n=read();m=read();

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

{

int x=read();insert(x,i);

}

int tot=0;

for(int i=1;i<=m;i++)

{

int l=read(),r=read();

q[i].z=read();

a[++tot].p=l-1;a[tot].num=i;a[tot].flag=0;

a[++tot].p=r;a[tot].num=i;a[tot].flag=1;

}

build(1,1,n);

sort(a+1,a+tot+1);

dfs1(0);dfs2(0,0);

int now=-1;

for(int i=1;i<=tot;i++)

{

while(now<a[i].p)

{

now++;

solve_update(now,0);

}

int t=a[i].num;

if(!a[i].flag)q[t].ans1=solve_query(q[t].z,0);

else q[t].ans2=solve_query(q[t].z,0);

}

for(int i=1;i<=m;i++)

printf("%d\n",(q[i].ans2-q[i].ans1+mod)%mod);

return 0;

}

« 「BZOJ2325」[ZJOI2011] 道馆之战「BZOJ1935」[SHOI2007] Tree 园丁的烦恼 »

OKAYABOOD

思路很清晰，谢谢

limfc

跪跪跪orz

斯巴达临时工

跪跪跪orz

褚步霄

跪跪跪orz

Clare

跪跪跪orz

跪跪跪orz

跪跪跪orz

跪跪跪orz

跪跪跪orz

跪跪跪orz

hzwer.com _ Home | http://hzwer.com

「BZOJ3626」[LNOI2014] LCA

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论