树剖板子 19pts 求调

Decompose @ 2023-11-04 09:27:19

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll a=0,x=1;
    char c=getchar();
    while (!isdigit(c)){
        if (c=='-')
            x=-x;
        c=getchar();
    }
    while (isdigit(c)){
        a=a*10+c-'0';
        c=getchar();
    }
    return x*a;
}
int n,c=0,hd[100001],nt[200001],to[200001],fa[100001],sn[100001],sz[100001],dh[100001],id[100001],tp[100001];
ll md,k[100001],s[400001],t[400001],wt[100001];
ll plus(ll x,ll y){
    return (x%md+y%md)%md;
}
inline int lc(int x){
    return x<<1;
}
inline int rc(int x){
    return (x<<1)|1;
}
inline void push_up(int p){
    s[p]=plus(s[lc(p)],s[rc(p)]);
    return;
}
void build(int p,int l,int r){
    int m=(l+r)>>1;
    if (l==r){
        s[p]=k[l];
        return;
    }
    build(lc(p),l,m);
    build(rc(p),m+1,r);
    push_up(p);
    return;
}
inline void f(int p,int l,int r,ll x){
    t[p]=plus(t[p],x);
    s[p]=plus(s[p],(x%p)*((r-l+1)%p)%p);
    return;
}
void push_down(int p,int l,int r){
    int m=(l+r)>>1;
    f(lc(p),l,m,t[p]);
    f(rc(p),m+1,r,t[p]);
    t[p]=0;
    return;
}
void add(int nl,int nr,int p,int l,int r,ll x){
    int m=(l+r)>>1;
    if ((nl<=l)&&(nr>=r)){
        f(p,l,r,x);
        return;
    }
    push_down(p,l,r);
    if (nl<=m)
        add(nl,nr,lc(p),l,m,x);
    if (nr>m)
        add(nl,nr,rc(p),m+1,r,x);
    push_up(p);
    return;
}
ll sum(int nl,int nr,int p,int l,int r){
    int m=(l+r)>>1;
    ll a=0;
    if ((nl<=l)&&(nr>=r))
        return s[p];
    push_down(p,l,r);
    if (nl<=m)
        a=plus(a,sum(nl,nr,lc(p),l,m));
    if (nr>m)
        a=plus(a,sum(nl,nr,rc(p),m+1,r));
    return a;
}
inline void add_edge(int x,int y){
    nt[++c]=hd[x];
    hd[x]=c;
    to[c]=y;
    nt[++c]=hd[y];
    hd[y]=c;
    to[c]=x;
    return;
}
//----------以上部分大概率没错----------
void dfs1(int x,int f,int d){
    int mx=0;
    fa[x]=f;
    dh[x]=d;
    sz[x]=1;
    for (int i=hd[x];i;i=nt[i])
        if (to[i]!=f){
            dfs1(to[i],x,d+1);
            sz[x]+=sz[to[i]];
            if (sz[to[i]]>mx){
                mx=sz[to[i]];
                sn[x]=to[i];
            }
        }
    return;
}
void dfs2(int x,int f){
    id[x]=++c;
    k[c]=wt[x];
    tp[x]=f;
    if (!sn[x])
        return;
    dfs2(sn[x],f);
    for (int i=hd[x];i;i=nt[i])
        if ((to[i]!=fa[x])&&(to[i]!=sn[x]))
            dfs2(to[i],to[i]);
    return;
}
void add1(int x,int y,ll z){
    z%=md;
    while (tp[x]!=tp[y]){
        if (dh[tp[x]]<dh[tp[y]])
            swap(x,y);
        add(id[x],id[tp[x]],1,1,n,z);
        x=fa[tp[x]];
    }
    if (dh[x]<dh[y])
        swap(x,y);
    add(id[x],id[y],1,1,n,z);
    return;
}
ll sum1(int x,int y){
    ll as=0;
    while (tp[x]!=tp[y]){
        if (dh[tp[x]]<dh[tp[y]])
            swap(x,y);
        as=plus(as,sum(id[x],id[tp[x]],1,1,n));
        x=fa[tp[x]];
    }
    if (dh[x]>dh[y])
        swap(x,y);
    as=plus(as,sum(id[x],id[y],1,1,n));
    return as%md;
}
void add2(int x,ll y){
    y%=md;
    add(id[x],id[x]+sz[x]-1,1,1,n,y);
    return;
}
ll sum2(int x){
    return sum(id[x],id[x]+sz[x]-1,1,1,n)%md;
}
signed main(){
    int m,r,u,v,o,a,b,f;
    n=read();
    m=read();
    r=read();
    md=read();
    for (int i=1;i<=n;++i)
        wt[i]=read();
    for (int i=1;i<n;++i){
        u=read();
        v=read();
        add_edge(u,v);
    }
    dfs1(r,0,1);
    c=0;
    dfs2(r,r);
    build(1,1,n);
    for (int i=1;i<=m;++i){
        o=read();
        a=read();
        if (o==1){
            b=read();
            f=read();
            add1(a,b,f);
        }
        else if (o==2){
            b=read();
            printf("%lld\n",sum1(a,b));
        }
        else if (o==3){
            b=read();
            add2(a,b);
        }
        else
            printf("%lld\n",sum2(a));
    }
    return 0;
}

by __mcx_ @ 2023-11-04 09:54:29

修改函数左右区间端点反了 例如

add(id[x],id[tp[x]],1,1,n,z);

因为你的 dep_{top(x)} < dep_x 所以理论来说 dfn_{top(x)} < dfn_x

x，y在同一条链上的情况类似

by __mcx_ @ 2023-11-04 09:56:25

怎么add函数里面同一条链的情况是反的，sum1函数里面的情况又是对的。。。

by Decompose @ 2023-11-04 10:06:14

@_mcx thx，我是傻逼

by Decompose @ 2023-11-04 10:09:32

但为什么改了之后还是 19pts 啊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll a=0,x=1;
    char c=getchar();
    while (!isdigit(c)){
        if (c=='-')
            x=-x;
        c=getchar();
    }
    while (isdigit(c)){
        a=a*10+c-'0';
        c=getchar();
    }
    return x*a;
}
int n,c=0,hd[100001],nt[200001],to[200001],fa[100001],sn[100001],sz[100001],dh[100001],id[100001],tp[100001];
ll md,k[100001],s[400001],t[400001],wt[100001];
ll plus(ll x,ll y){
    return (x%md+y%md)%md;
}
inline int lc(int x){
    return x<<1;
}
inline int rc(int x){
    return (x<<1)|1;
}
inline void push_up(int p){
    s[p]=plus(s[lc(p)],s[rc(p)]);
    return;
}
void build(int p,int l,int r){
    int m=(l+r)>>1;
    if (l==r){
        s[p]=k[l];
        return;
    }
    build(lc(p),l,m);
    build(rc(p),m+1,r);
    push_up(p);
    return;
}
inline void f(int p,int l,int r,ll x){
    t[p]=plus(t[p],x);
    s[p]=plus(s[p],(x%p)*((r-l+1)%p)%p);
    return;
}
void push_down(int p,int l,int r){
    int m=(l+r)>>1;
    f(lc(p),l,m,t[p]);
    f(rc(p),m+1,r,t[p]);
    t[p]=0;
    return;
}
void add(int nl,int nr,int p,int l,int r,ll x){
    int m=(l+r)>>1;
    if ((nl<=l)&&(nr>=r)){
        f(p,l,r,x);
        return;
    }
    push_down(p,l,r);
    if (nl<=m)
        add(nl,nr,lc(p),l,m,x);
    if (nr>m)
        add(nl,nr,rc(p),m+1,r,x);
    push_up(p);
    return;
}
ll sum(int nl,int nr,int p,int l,int r){
    int m=(l+r)>>1;
    ll a=0;
    if ((nl<=l)&&(nr>=r))
        return s[p];
    push_down(p,l,r);
    if (nl<=m)
        a=plus(a,sum(nl,nr,lc(p),l,m));
    if (nr>m)
        a=plus(a,sum(nl,nr,rc(p),m+1,r));
    return a;
}
inline void add_edge(int x,int y){
    nt[++c]=hd[x];
    hd[x]=c;
    to[c]=y;
    nt[++c]=hd[y];
    hd[y]=c;
    to[c]=x;
    return;
}
void dfs1(int x,int f,int d){
    int mx=0;
    fa[x]=f;
    dh[x]=d;
    sz[x]=1;
    for (int i=hd[x];i;i=nt[i])
        if (to[i]!=f){
            dfs1(to[i],x,d+1);
            sz[x]+=sz[to[i]];
            if (sz[to[i]]>mx){
                mx=sz[to[i]];
                sn[x]=to[i];
            }
        }
    return;
}
void dfs2(int x,int f){
    id[x]=++c;
    k[c]=wt[x];
    tp[x]=f;
    if (!sn[x])
        return;
    dfs2(sn[x],f);
    for (int i=hd[x];i;i=nt[i])
        if ((to[i]!=fa[x])&&(to[i]!=sn[x]))
            dfs2(to[i],to[i]);
    return;
}
void add1(int x,int y,ll z){
    z%=md;
    while (tp[x]!=tp[y]){
        if (dh[tp[x]]<dh[tp[y]])
            swap(x,y);
        add(id[tp[x]],id[x],1,1,n,z);
        x=fa[tp[x]];
    }
    if (dh[x]>dh[y])
        swap(x,y);
    add(id[x],id[y],1,1,n,z);
    return;
}
ll sum1(int x,int y){
    ll as=0;
    while (tp[x]!=tp[y]){
        if (dh[tp[x]]<dh[tp[y]])
            swap(x,y);
        as=plus(as,sum(id[tp[x]],id[x],1,1,n));
        x=fa[tp[x]];
    }
    if (dh[x]>dh[y])
        swap(x,y);
    as=plus(as,sum(id[x],id[y],1,1,n));
    return as%md;
}
void add2(int x,ll y){
    y%=md;
    add(id[x],id[x]+sz[x]-1,1,1,n,y);
    return;
}
ll sum2(int x){
    return sum(id[x],id[x]+sz[x]-1,1,1,n)%md;
}
signed main(){
    int m,r,u,v,o,a,b,f;
    n=read();
    m=read();
    r=read();
    md=read();
    for (int i=1;i<=n;++i)
        wt[i]=read();
    for (int i=1;i<n;++i){
        u=read();
        v=read();
        add_edge(u,v);
    }
    dfs1(r,0,1);
    c=0;
    dfs2(r,r);
    build(1,1,n);
    for (int i=1;i<=m;++i){
        o=read();
        a=read();
        if (o==1){
            b=read();
            f=read();
            add1(a,b,f);
        }
        else if (o==2){
            b=read();
            printf("%lld\n",sum1(a,b));
        }
        else if (o==3){
            b=read();
            add2(a,b);
        }
        else
            printf("%lld\n",sum2(a));
    }
    return 0;
}

by Decompose @ 2023-11-04 10:13:39

好吧，是取摸的时候变量名弄混了，我是傻逼，此贴结。