星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P3384 【【模板】树链剖分】

posted on 2017-10-11 21:22:04 | under 题解 |

本题是树链剖分的裸题。虽然大家都知道,树状数组的常数比较小,但由于太难写了,于是大部分人也都是写的线段树。

我的代码163行,而这个行数是纯天然缩行形成的,也就是说通过人工压缩可以压到150行以内。

而且这个代码实际上还是长了。为什么呢?因为我用了许多if来取模。

不开long long的原因是在Linux下long long会变得特别慢,而线段树常数也比较大。

而如果有时候不分青红皂白直接取模就会导致有时候会变得比较慢,某些题目会故意这样来卡常数。

此外注意等于mod数也要取模。

实测比我的同学快300ms。

主要是讲述以上的优化思路,代码仅供参考,每个人的代码风格都不一样,重要的是细心。

#include<cstdio>
#include<iostream>
#define neko 100010
#define meko 100010
#define mid ((l+r)>>1)
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define ori tagl,tagr
#define f(i,a,b) for(register int i=a;i<=b;++i)
using std::swap;
int Sum[neko<<2],Add[neko<<2];
typedef int arr[neko];
int n,m,root,mod,t,cnt;
arr siz,fa,son,top,dep,w,head,ord,a;
//first dfs: siz fa son dep
//second dfs: top
struct node
{
    int u,v,next;
}e[meko<<1];
void read(int &x)
{
    char c=getchar();int p=1;x=0;
    while(!isdigit(c)){c=getchar();if(c=='-')p=-1;}
    while(isdigit(c))
    {
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }x*=p;
}
void add(int x,int y)
{
    e[++t].u=x;
    e[t].v=y;
    e[t].next=head[x];
    head[x]=t;
}
void dfs(int u)//其实这是树剖最容易打的地方
{
    dep[u]=dep[fa[u]]+1;
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v!=fa[u])
        {
            fa[v]=u;
            dfs(v);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[v]>siz[son[u]])son[u]=v;
        }
    }
}
void dfs2(int u)
{
    w[u]=++cnt;
    ord[cnt]=u;
    if(u==son[fa[u]])top[u]=top[fa[u]];
    else top[u]=u;
    if(son[u]!=-1)dfs2(son[u]);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v!=fa[u]&&v!=son[u])dfs2(v);
    }
}
void pushup(int root)
{
    Sum[root]=Sum[root<<1]+Sum[root<<1|1];
    if(Sum[root]>=mod)Sum[root]%=mod;    
}
void build(int root,int l,int r)
{
    if(l==r)Sum[root]=a[ord[l]];
    else
    {
        build(lson);
        build(rson);
        pushup(root);
    }
}
void pushdown(int root,int l,int r)
{
    if(Add[root])
    {
        Add[root<<1]+=Add[root];
        Add[root<<1|1]+=Add[root];
        if(Add[root<<1]>=mod)Add[root<<1]%=mod;
        if(Add[root<<1|1]>=mod)Add[root<<1|1]%=mod;
        Sum[root<<1]+=(mid-l+1)*Add[root];
        Sum[root<<1|1]+=(r-mid)*Add[root];
        if(Sum[root<<1]>=mod)Sum[root<<1]%=mod;
        if(Sum[root<<1|1]>=mod)Sum[root<<1|1]%=mod;
        Add[root]=0;
    }
}
void update(int root,int l,int r,int tagl,int tagr,int x)
{
    if(l>=tagl&&r<=tagr)
    {
        Add[root]+=x;
        Sum[root]+=(r-l+1)*x;
        if(Sum[root]>=mod)Sum[root]%=mod;
    }
    else
    {
        pushdown(root,l,r);
        if(tagl<=mid)update(lson,ori,x);
        if(tagr>mid)update(rson,ori,x);
        pushup(root);
    }
}
int query(int root,int l,int r,int tagl,int tagr)
{
    if(l>=tagl&&r<=tagr)return Sum[root];
    else
    {
        pushdown(root,l,r);
        int tmp=0;
        if(tagl<=mid)tmp+=query(lson,ori);
        if(tmp>=mod)tmp%=mod;
        if(tagr>mid)tmp+=query(rson,ori);
        return tmp>=mod?tmp%mod:tmp;
    }
}
void pathu(int l,int r,int x)
{
    while(top[l]!=top[r])
    {
        if(dep[top[l]]<dep[top[r]])swap(l,r);
        update(1,1,n,w[top[l]],w[l],x);
        l=fa[top[l]];
    }if(dep[l]>dep[r])swap(l,r);
    update(1,1,n,w[l],w[r],x);
}
int pathq(int l,int r)
{
    int sum=0;
    while(top[l]!=top[r])
    {
        if(dep[top[l]]<dep[top[r]])swap(l,r);
        sum+=query(1,1,n,w[top[l]],w[l]);if(sum>=mod)sum%=mod;
        l=fa[top[l]];
    }if(dep[l]>dep[r])swap(l,r);
    return (sum+query(1,1,n,w[l],w[r]))%mod;
}
int main()
{
    int _,_2,_3,_4,x,y;
    read(n),read(m),read(root),read(mod);
    f(i,1,n)read(a[i]),son[i]=-1;
    f(i,1,n-1)read(x),read(y),add(x,y),add(y,x);
    dfs(root);
    dfs2(root);
    build(1,1,n);
    f(i,1,m)
    {
        read(_),read(_2);
        if(_==1)read(_3),read(_4),pathu(_2,_3,_4);
        if(_==2)read(_3),printf("%d\n",pathq(_2,_3));
        if(_==3)read(_3),update(1,1,n,w[_2],w[_2]+siz[_2]-1,_3);
        if(_==4)printf("%d\n",query(1,1,n,w[_2],w[_2]+siz[_2]-1));
    }return 0;
}