注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

jytnb1的博客

日影斑驳,朽日浮尘;韶光荏苒,逡巡不前。

 
 
 

日志

 
 
关于我

有志者,事竟成,苦心人,天不负。

网易考拉推荐

【bzoj】3626: [LNOI2014]LCA  

2015-10-24 20:37:56|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
为什么我做的题目越来越水了,都不想写题解,感觉配不上日志的开篇了。【bzoj】3626: [LNOI2014]LCA - jytnb1 - jytnb1的博客我怎么这么弱,模板题刷刷有什么意思。顶多练一下打字速度。
题目链接:BZOJ3626

3626: [LNOI2014]LCA

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 996  Solved: 341
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
===========================================================================
做法很简单,离线做。考虑怎么求deep(lca(i,z))。如图(看不清可以放大),我们假设i是10号节点,z是4号节点,首先,我们先让10号点所有的祖先都+1,即根节点(1号点)到i(10号点)的路径上的点都+1,那么deep(lca(i,z))就是很节点(1号点)到z(4号点)的点权和(即v[1]+v[2]=2)。
【bzoj】3626: [LNOI2014]LCA - jytnb1 - jytnb1的博客【bzoj】3626: [LNOI2014]LCA - jytnb1 - jytnb1的博客【bzoj】3626: [LNOI2014]LCA - jytnb1 - jytnb1的博客


这样的话,思路大致清晰了,我们可以枚举i,让i所有的祖先(即根到i的路径上的点的点权)都+1,对于每一个询问,在枚举i的过程顺便求出
【bzoj】3626: [LNOI2014]LCA - jytnb1 - jytnb1的博客【bzoj】3626: [LNOI2014]LCA - jytnb1 - jytnb1的博客
该询问的答案就是【bzoj】3626: [LNOI2014]LCA - jytnb1 - jytnb1的博客
之后就是树剖的事了。
===========================================================================

#include<cstdio>
using namespace std;
const int N=50050,Mod=201314;
int i,j,k,n,q,l,r,z,En,ch,x,Qn,Pn,t;
int h[N],H[N];
struct num {int l,r;} A[N];
struct edge1 {int n,s;} E[N];
struct edge2 {int n,s,v;} Q[N<<1];
struct tree {int ad,sm;} T[N<<2];
struct point {int fa,sz,sn,dp,fv,tp;} P[N<<1];
void R(int &x)
{
x=0;ch=getchar();
while (ch<'0' || '9'<ch) ch=getchar();
while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
}
void E_add(int x,int y)
{
En++;E[En].s=y;
E[En].n=h[x];h[x]=En;
}
void Q_add(int x,int y,int v)
{
Qn++;Q[Qn].s=y;Q[Qn].v=v;
Q[Qn].n=H[x];H[x]=Qn;
}
void dfs1(int x,int F)
{
P[x].fa=F;P[x].sz=1;P[x].dp=P[F].dp+1;
int ma=0,k;
for (k=h[x];k;k=E[k].n)
{
dfs1(E[k].s,x);
P[x].sz+=P[E[k].s].sz;
if (P[E[k].s].sz>ma)
{
ma=P[E[k].s].sz;
P[x].sn=E[k].s;
}
}
}
void dfs2(int x,int tp)
{
P[x].tp=tp;P[x].fv=++Pn;
if (P[x].sn) dfs2(P[x].sn,tp);
for (int k=h[x];k;k=E[k].n) if (E[k].s!=P[x].sn) dfs2(E[k].s,E[k].s);
}
void down(int L,int R,int k)
{
if (T[k].ad)
{
int mid=(L+R)>>1;
(T[k<<1].ad+=T[k].ad)%=Mod;
(T[k<<1|1].ad+=T[k].ad)%=Mod;
(T[k<<1].sm+=1ll*T[k].ad*(mid-L+1)%Mod)%=Mod;
(T[k<<1|1].sm+=1ll*T[k].ad*(R-mid)%Mod)%=Mod;
T[k].ad=0;
}
}
void up(int k)
{
T[k].sm=T[k<<1].sm+T[k<<1|1].sm;
}
void T_add(int L,int R,int l,int r,int ad,int k)
{
if (L==l && R==r)
{
(T[k].sm+=1ll*ad*(R-L+1)%Mod)%=Mod;
(T[k].ad+=ad)%=Mod;
return;
}
down(L,R,k);
int mid=(L+R)>>1;
if (r<=mid) T_add(L,mid,l,r,ad,k<<1);
else
{
if (l>mid) T_add(mid+1,R,l,r,ad,k<<1|1);
else T_add(L,mid,l,mid,ad,k<<1),T_add(mid+1,R,mid+1,r,ad,k<<1|1);
}
up(k);
}
int T_query(int L,int R,int l,int r,int k)
{
if (L==l && R==r) return T[k].sm;
down(L,R,k);
int mid=(L+R)>>1;
if (r<=mid) return T_query(L,mid,l,r,k<<1);
if (l>mid) return T_query(mid+1,R,l,r,k<<1|1);
return (T_query(L,mid,l,mid,k<<1)+T_query(mid+1,R,mid+1,r,k<<1|1))%Mod;
}
int main()
{
R(n);R(q);
for (i=2;i<=n;i++)
{
R(x);x++;
E_add(x,i);
}
dfs1(1,0);dfs2(1,1);
for (i=1;i<=q;i++)
{
R(l);R(r);R(z);
r++;z++;
if (l) Q_add(l,z,i);
Q_add(r,z,i);
}
for (i=1;i<=n;i++)
{
x=i;
while (P[x].tp!=1)
{
T_add(1,n,P[P[x].tp].fv,P[x].fv,1,1);
x=P[P[x].tp].fa;
}
T_add(1,n,P[1].fv,P[x].fv,1,1);
for (k=H[i];k;k=Q[k].n)
{
x=Q[k].s;t=0;
while (P[x].tp!=1)
{
(t+=T_query(1,n,P[P[x].tp].fv,P[x].fv,1))%=Mod;
x=P[P[x].tp].fa;
}
(t+=T_query(1,n,P[1].fv,P[x].fv,1))%=Mod;
j=Q[k].v;
A[j].l=A[j].r;
A[j].r=t;
}
}
for (i=1;i<=q;i++) printf("%d\n",(A[i].r+Mod-A[i].l)%Mod);
}

   
  评论这张
 
阅读(33)| 评论(8)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017