洛谷 3398 仓鼠找sugar——树链剖分

题目:https://www.luogu.org/problemnew/show/P3398

原来只要把值记录成第几次就行了。

别忘了while(top[a]!=top[b])之后还要走一步。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+;
int n,q,hd[N],xnt,nxt[N<<],to[N<<],tim,top[N],fa[N],siz[N],son[N],dep[N],rnk[N];
int ls[N<<],rs[N<<],val[N<<],laz[N<<];
int rdn()
{
int ret=;char ch=getchar();
while(ch>''||ch<'')ch=getchar();
while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();
return ret;
}
void add(int x,int y)
{
to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;
to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;
}
void dfs(int cr,int f)
{
fa[cr]=f;dep[cr]=dep[f]+;siz[cr]=;
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=f)
{
dfs(v,cr);siz[cr]+=siz[v];
if(siz[v]>siz[son[cr]])son[cr]=v;
}
}
void dfs(int cr)
{
rnk[cr]=++tim;
if(son[cr])top[son[cr]]=top[cr],dfs(son[cr]);
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa[cr]&&v!=son[cr])
{top[v]=v;dfs(v);}
}
void build(int l,int r,int cr)
{
val[cr]=N;laz[cr]=N;
if(l==r)return;int mid=l+r>>;
ls[cr]=++tim;build(l,mid,ls[cr]);
rs[cr]=++tim;build(mid+,r,rs[cr]);
}
void pshd(int cr)
{
if(laz[cr]==N)return;
laz[ls[cr]]=laz[rs[cr]]=val[ls[cr]]=val[rs[cr]]=laz[cr];
laz[cr]=N;
}
void pshp(int cr)
{
val[cr]=min(val[ls[cr]],val[rs[cr]]);
}
void mdfy(int l,int r,int cr,int L,int R,int w)
{
// printf("mdfy L=%d R=%d l=%d r=%d val=%d w=%d\n",L,R,l,r,val[cr],w);
if(l>=L&&r<=R){val[cr]=laz[cr]=w;return;}
int mid=l+r>>;pshd(cr);
if(L<=mid)mdfy(l,mid,ls[cr],L,R,w);
if(mid<R)mdfy(mid+,r,rs[cr],L,R,w);
pshp(cr);
}
void mdfy(int a,int b,int w)
{
while(top[a]!=top[b])
{
if(dep[top[a]]>dep[top[b]])swap(a,b);
mdfy(,n,,rnk[top[b]],rnk[b],w);b=fa[top[b]];
}
if(dep[a]>dep[b])swap(a,b);
mdfy(,n,,rnk[a],rnk[b],w);
}
bool query(int l,int r,int cr,int L,int R)
{
// printf("query L=%d R=%d l=%d r=%d val=%d laz=%d\n",L,R,l,r,val[cr],laz[cr]);
if(l>=L&&r<=R)return val[cr]==q;
int mid=l+r>>;pshd(cr);
bool ret=;
if(L<=mid)ret|=query(l,mid,ls[cr],L,R);
if(mid<R)ret|=query(mid+,r,rs[cr],L,R);
return ret;
}
bool query(int a,int b)
{
bool ret=;
while(top[a]!=top[b])
{
if(dep[top[a]]>dep[top[b]])swap(a,b);
ret|=query(,n,,rnk[top[b]],rnk[b]);b=fa[top[b]];
}
if(dep[a]>dep[b])swap(a,b);
ret|=query(,n,,rnk[a],rnk[b]);
return ret;
}
int main()
{
n=rdn();q=rdn();int a,b,c,d;
for(int i=;i<n;i++)
{
a=rdn();b=rdn();add(a,b);
}
dfs(,);top[]=;dfs();
tim=;val[]=N;build(,n,);
while(q--)
{
// printf("q=%d\n",q);
a=rdn();b=rdn();c=rdn();d=rdn();
mdfy(a,b,q);
if(query(c,d))puts("Y");else puts("N");
}
return ;
}
上一篇:洛谷p3398仓鼠找suger题解


下一篇:php memcache分布式和要注意的问题