Loading...

树链剖分 洛谷P3384

check评论:0 条 remove_red_eye浏览量:421 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-06-24

qwq我太菜啦
这一道题调了两周欸qwq
主要理一下思路:

  • 划分出重链,用线段树维护
  • 链修改就是一直修改两个点各自所在重链直到他们在一条重链(top相等)上,链查询基本相同
  • dfs1要处理出每个点的fa,dep,son,siz
  • dfs2要处理出每个点的in,out,seg,top
    qwq差不多就这么多啦

code:

#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define maxn 200001
int seg[maxn],in[maxn],out[maxn],dep[maxn],fa[maxn],top[maxn],son[maxn],siz[maxn];
int head[maxn],sum[maxn<<2],addv[maxn<<2],a[maxn];
struct edge
{
    int next,to;
}e[maxn<<1];
int tot=0;
void add(int u,int v)
{
    tot++;
    e[tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;
}
void dfs1(int u)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u])
        {
            continue;
        }
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
        {
            son[u]=v;
        }
    }
}
void dfs2(int u,int tp)
{
    tot++;
    in[u]=tot;
    seg[tot]=u;
    top[u]=tp;
    if(son[u])
    {
        dfs2(son[u],tp);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u]||v==son[u])
        {
            continue;
        }
        dfs2(v,v);
    }
    out[u]=tot;
}
int n,m,r,p;
#define pushup(o) sum[o]=(sum[o<<1]+sum[o<<1|1])%p 
void build(int o,int lf,int rg)
{
    if(lf==rg)
    {
        sum[o]=a[seg[lf]];
        return ;
    }
    int mid=(lf+rg)>>1;
    build(o<<1,lf,mid);
    build(o<<1|1,mid+1,rg);
    pushup(o);
}
void pushdown(int o,int lf,int rg)
{
    if(addv[o])
    {
        int mid=(lf+rg)>>1;
        sum[o<<1]=(sum[o<<1]+(mid-lf+1)*addv[o])%p;
        sum[o<<1|1]=(sum[o<<1|1]+(rg-mid)*addv[o])%p;
        addv[o<<1]+=addv[o];
        addv[o<<1|1]+=addv[o];
        addv[o]=0;
    }
}
void modify(int o,int lf,int rg,int l,int r,int x)
{
    if(l<=lf&&rg<=r)
    {
        sum[o]=(sum[o]+(rg-lf+1)*x)%p;
        addv[o]+=x;
        return ;
    }
    pushdown(o,lf,rg);
    int mid=(lf+rg)>>1;
    if(l<=mid)
    {
        modify(o<<1,lf,mid,l,r,x);
    }
    if(mid<r)
    {
        modify(o<<1|1,mid+1,rg,l,r,x);
    }
    pushup(o);
}
int query(int o,int lf,int rg,int l,int r)
{
    if(l<=lf&&rg<=r)
    {
        return sum[o];
    }
    pushdown(o,lf,rg);
    int ans=0;
    int mid=(lf+rg)>>1;
    if(l<=mid)
    {
        ans=(ans+query(o<<1,lf,mid,l,r))%p;
    }
    if(mid<r)
    {
        ans=(ans+query(o<<1|1,mid+1,rg,l,r))%p;
    }
    return ans;
}
void mpath(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        {
            swap(x,y);
        }
        modify(1,1,n,in[top[x]],in[x],z);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    modify(1,1,n,in[y],in[x],z);
}
int qpath(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        {
            swap(x,y);
        }
        ans=(ans+query(1,1,n,in[top[x]],in[x]))%p;
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    ans=(ans+query(1,1,n,in[y],in[x]))%p;
    return ans;
}
int main()
{
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    tot=0;
    dep[r]=1;
    dfs1(r);
    tot=0;
    dfs2(r,r);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int opt,x,y,z;
        scanf("%d",&opt);
        switch(opt)
        {
            case 1:scanf("%d%d%d",&x,&y,&z);mpath(x,y,z);break;
            case 2:scanf("%d%d",&x,&y);printf("%d\n",qpath(x,y));break;
            case 3:scanf("%d%d",&x,&y);modify(1,1,n,in[x],out[x],y);break;
            case 4:scanf("%d",&x);printf("%d\n",query(1,1,n,in[x],out[x]));break;
        }
    }
}

chevron_left 代码风格有关
选择客栈 洛谷P1311 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名