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

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

树链剖分一下，路径就变成线段树上的几个区间；

两条路径相交就是线段树上有区间相交，所以在相应位置打个标记，查询有无标记即可；

一开始是打1的标记，查询后就减去，查询 sum 是否为 0 即可；

然而这样写却全 WA 了...悲痛欲绝去看了 TJ ，模仿了其写法，回头再看发现是忘记写 pushdown ，而且 -1 的地方写成 0 了囧...

改掉就 A 了，这个做法完全没问题嘛！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=1e5+;

int n,q,hd[maxn],ct,sum[maxn<<],tim,fa[maxn],lzy[maxn<<];

int dep[maxn],dfn[maxn],top[maxn],son[maxn],siz[maxn],id[maxn];

struct N{

    int to,nxt;

    N(int t=,int n=):to(t),nxt(n) {}

}ed[maxn<<];

void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}

void dfs(int x,int f)

{

    dep[x]=dep[f]+; siz[x]=; fa[x]=f;

    for(int i=hd[x],u;i;i=ed[i].nxt)

    {

        if((u=ed[i].to)==f)continue;

        dfs(u,x); siz[x]+=siz[u];

        if(siz[u]>siz[son[x]])son[x]=u;

    }

}

void dfs2(int x)

{

    dfn[x]=++tim; id[tim]=x;//

    if(son[x])top[son[x]]=top[x],dfs2(son[x]);

    for(int i=hd[x],u;i;i=ed[i].nxt)

    {

        if((u=ed[i].to)==fa[x]||u==son[x])continue;

        top[u]=u; dfs2(u);

    }

}

void pushup(int x){sum[x]=sum[x<<]+sum[x<<|];}

void pushdown(int x,int l,int r)

{

    if(!lzy[x])return;

    int ls=(x<<),rs=(x<<|),mid=((l+r)>>);

    lzy[ls]+=lzy[x]; lzy[rs]+=lzy[x];

    sum[ls]+=lzy[x]*(mid-l+); sum[rs]+=lzy[x]*(r-mid);

    lzy[x]=;

}

void add(int x,int l,int r,int L,int R,int val)

{

    if(l>=L&&r<=R){sum[x]+=val*(r-l+); lzy[x]+=val; return;}

    pushdown(x,l,r);//

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

    if(mid>=L)add(x<<,l,mid,L,R,val);

    if(mid<R)add(x<<|,mid+,r,L,R,val);

    pushup(x);

}

int ask(int x,int l,int r,int L,int R)

{

    if(l>=L&&r<=R)return sum[x];

    pushdown(x,l,r);//

    int ret=,mid=((l+r)>>);

    if(mid>=L)ret+=ask(x<<,l,mid,L,R);

    if(mid<R)ret+=ask(x<<|,mid+,r,L,R);

    return ret;

}

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

{

    while(top[x]!=top[y])

    {

        if(dep[top[x]]<dep[top[y]])swap(x,y);

        add(,,n,dfn[top[x]],dfn[x],val);

        x=fa[top[x]];

    }

    if(dep[x]<dep[y])swap(x,y);

    add(,,n,dfn[y],dfn[x],val);

}

bool query(int x,int y)

{

    while(top[x]!=top[y])

    {

        if(dep[top[x]]<dep[top[y]])swap(x,y);

        if(ask(,,n,dfn[top[x]],dfn[x])) return ;

        x=fa[top[x]];

    }

    if(dep[x]<dep[y])swap(x,y);

    return ask(,,n,dfn[y],dfn[x]);

}

int main()

{

    scanf("%d%d",&n,&q);

    for(int i=,x,y;i<n;i++)

    {

        scanf("%d%d",&x,&y);

        add(x,y); add(y,x);

    }

    dfs(,); top[]=; dfs2();

    for(int i=,a,b,c,d;i<=q;i++)

    {

        scanf("%d%d%d%d",&a,&b,&c,&d);

        update(a,b,);

        if(query(c,d))printf("Y\n");

        else printf("N\n");

        update(a,b,-);//!0

    }

    return ;

}

还有 TJ 写法，就是不删除了，打个 int 类型的标记，所以查询 max 即可。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=1e5+;

int n,q,hd[maxn],ct,mx[maxn<<],tim,fa[maxn],lzy[maxn<<],tot;

int dep[maxn],dfn[maxn],top[maxn],son[maxn],siz[maxn],id[maxn];

struct N{

    int to,nxt;

    N(int t=,int n=):to(t),nxt(n) {}

}ed[maxn<<];

void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}

void dfs(int x,int f)

{

    dep[x]=dep[f]+; siz[x]=; fa[x]=f;

    for(int i=hd[x],u;i;i=ed[i].nxt)

    {

        if((u=ed[i].to)==f)continue;

        dfs(u,x); siz[x]+=siz[u];

        if(siz[u]>siz[son[x]])son[x]=u;

    }

}

void dfs2(int x)

{

    dfn[x]=++tim; id[tim]=x;//

    if(son[x])top[son[x]]=top[x],dfs2(son[x]);

    for(int i=hd[x],u;i;i=ed[i].nxt)

    {

        if((u=ed[i].to)==fa[x]||u==son[x])continue;

        top[u]=u; dfs2(u);

    }

}

void pushup(int x){mx[x]=max(mx[x<<],mx[x<<|]);}

void pushdown(int x)

{

    if(!lzy[x])return;

    lzy[x<<]=lzy[x<<|]=lzy[x];

    mx[x<<]=mx[x<<|]=lzy[x];

    lzy[x]=;

}

void add(int x,int l,int r,int L,int R,int val)

{

    if(l>=L&&r<=R){mx[x]=lzy[x]=val; return;}

    pushdown(x);

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

    if(mid>=L)add(x<<,l,mid,L,R,val);

    if(mid<R)add(x<<|,mid+,r,L,R,val);

    pushup(x);

}

int ask(int x,int l,int r,int L,int R)

{

    if(l>=L&&r<=R)return mx[x];

    pushdown(x);

    int ret=,mid=((l+r)>>);

    if(mid>=L)ret=max(ret,ask(x<<,l,mid,L,R));

    if(mid<R)ret=max(ret,ask(x<<|,mid+,r,L,R));

    return ret;

}

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

{

    while(top[x]!=top[y])

    {

        if(dep[top[x]]<dep[top[y]])swap(x,y);

        add(,,n,dfn[top[x]],dfn[x],val);

        x=fa[top[x]];

    }

    if(dep[x]<dep[y])swap(x,y);

    add(,,n,dfn[y],dfn[x],val);

}

bool query(int x,int y)

{

    while(top[x]!=top[y])

    {

        if(dep[top[x]]<dep[top[y]])swap(x,y);

        if(ask(,,n,dfn[top[x]],dfn[x])==tot) return ;

        x=fa[top[x]];

    }

    if(dep[x]<dep[y])swap(x,y);

    return (ask(,,n,dfn[y],dfn[x])==tot);

}

int main()

{

    scanf("%d%d",&n,&q);

    for(int i=,x,y;i<n;i++)

    {

        scanf("%d%d",&x,&y);

        add(x,y); add(y,x);

    }

    dfs(,); top[]=; dfs2();

    for(int i=,a,b,c,d;i<=q;i++)

    {

        scanf("%d%d%d%d",&a,&b,&c,&d);

        update(a,b,++tot);

        if(query(c,d))printf("Y\n");

        else printf("N\n");

    }

    return ;

}