[BZOJ4012/Luogu3241][HNOI2015]开店(树链剖分,主席树)

发布于 2018-01-28  54 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4012/Luogu3241][HNOI2015]开店(树链剖分,主席树)

Description

风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 n个地方,编号为 1 到 n,被 n-1 条带权的边连接起来。每个地方都住着一个妖怪,其中第 i 个地方的妖怪年龄是 x_i。妖怪都是些比较喜欢安静的家伙,所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样,兴趣点随着年龄的变化自然就会变化,比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现,基本上妖怪的兴趣只跟年龄有关,所以幽香打算选择一个地方 u(u为编号),然后在 u开一家面向年龄在 L到R 之间(即年龄大于等于 L、小于等于 R)的妖怪的店。也有可能 u这个地方离这些妖怪比较远,于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪,到点 u 的距离的和是多少(妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和) ,幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里,八云紫倒是准备了很多方案,于是幽香想要知道,对于每个方案,方便值是多少呢。

Http

BZOJ
Luogu

Tag

树链剖分,主席树

解决思路

先不考虑年龄的限制,考虑其它点\(x\)到一个指定点\(u\)的距离,设\(dis[i]\)表示点\(i\)到根(默认是\(1\))的距离,那么就是\(\sum dis[u]+dis[x]-2*dis[lca(u,x)]\),这个式子的前两项都比较好处理,一个直接用\(dis[u]\)乘以点数,另一个可以用前缀和维护,那么关键是\(dis[lca(u,x)]\)这一项怎么求。
这个的求法可以参考这一道题,类似的,我们用树链剖分+线段树的方法,对点\(x\)到根的路径的边都+1,这样查询\(u\)到根的路径和就可以得到\(dis[lca(u,x)]\)了。
最后把年龄的限制加上去,我们把妖怪按照年龄排序后,以此以树链剖分的形式插入主席树,这样就可以实现对年龄区间的查询。注意要标记永久化。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=150100;
const int maxM=maxN*2;
const int inf=2147483647;

class SegmentData
{
public:
    int ls,rs;
    ll sum;
    ll lazy;//懒标记,注意这里要永久化,不能下放
};

class Edge
{
public:
    ll v,w;
};

class Monster//妖怪
{
public:
    int id,age;
};

bool operator < (Monster A,Monster B)
{
    return A.age<B.age;
}

int n,m,Q,A;
Monster M[maxN];
int edgecnt=0,Head[maxN],Next[maxM];
Edge E[maxM];
int Dis[maxN],Size[maxN],Hson[maxN],Fa[maxN],Top[maxN];
int idcnt=0,Id[maxN];
int nodecnt=0,Root[maxN];
ll Dissum[maxN],Edgesum[maxN];//Dissum是每一个点到根的距离dis的前缀和,而Edgesum则是把一条边下放到它下面的那个点上的前缀和,后面这个是树链剖分要用到的
SegmentData S[maxN*130];

void dfs1(int u,int fa);
void dfs2(int u,int top);//两个树链剖分的dfs
void Build(int &now,int l,int r);
void Modify(int &now,int l,int r,int ql,int qr);//线段树区间修改
ll Query(int n1,int n2,int l,int r,int ql,int qr,ll lazy);//线段树区间查询

int main()
{
    mem(Head,-1);
    scanf("%d%d%d",&n,&Q,&A);
    for (int i=1;i<=n;i++) scanf("%d",&M[i].age),M[i].id=i;
    sort(&M[1],&M[n+1]);//将妖怪按照年龄排序
    for (int i=1;i<n;i++)//建树
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt]=(Edge){v,w};
        edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;E[edgecnt]=(Edge){u,w};
    }
    Dis[1]=0;//树链剖分初始化
    dfs1(1,0);
    dfs2(1,1);
    for (int i=1;i<=n;i++) Edgesum[i]+=Edgesum[i-1],Dissum[i]=Dissum[i-1]+Dis[M[i].id];//构造前缀和
    Build(Root[0],1,n);//主席树初始化
    for (int i=1;i<=n;i++)
    {
        int u=M[i].id;Root[i]=Root[i-1];
        while (Top[u]!=1) Modify(Root[i],1,n,Id[Top[u]],Id[u]),u=Fa[Top[u]];
        Modify(Root[i],1,n,1,Id[u]);
    }
    ll ans=0;
    while (Q--)//回答询问
    {
        int u,a,b;scanf("%d%d%d",&u,&a,&b);
        int L=(a+ans)%A,R=(b+ans)%A;if (L>R) swap(L,R);
        L=lower_bound(&M[1],&M[n+1],(Monster){0,L})-M;
        R=upper_bound(&M[1],&M[n+1],(Monster){0,R})-M-1;
        ll ret=0,uu=u;
        while (Top[uu]!=1)
            ret=ret+Query(Root[L-1],Root[R],1,n,Id[Top[uu]],Id[uu],0),uu=Fa[Top[uu]];
        ret=ret+Query(Root[L-1],Root[R],1,n,1,Id[uu],0);
        ans=(ll)(R-L+1)*Dis[u]+Dissum[R]-Dissum[L-1]-2*ret;
        printf("%lld\n",ans);
    }
    return 0;
}

void dfs1(int u,int fa)
{
    Size[u]=1;Fa[u]=fa;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (E[i].v!=fa)
        {
            Dis[E[i].v]=Dis[u]+E[i].w;
            dfs1(E[i].v,u);
            Size[u]+=Size[E[i].v];
            if (Size[E[i].v]>Size[Hson[u]]) Hson[u]=E[i].v;
        }
    return;
}

void dfs2(int u,int top)
{
    Id[u]=++idcnt;Top[u]=top;
    Edgesum[idcnt]=Dis[u]-Dis[Fa[u]];
    if (Hson[u]==0) return;
    dfs2(Hson[u],top);
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((E[i].v!=Fa[u])&&(E[i].v!=Hson[u]))
            dfs2(E[i].v,E[i].v);
    return;
}

void Build(int &now,int l,int r)
{
    now=++nodecnt;
    if (l==r) return;
    int mid=(l+r)>>1;
    Build(S[now].ls,l,mid);Build(S[now].rs,mid+1,r);
    return;
}

void Modify(int &now,int l,int r,int ql,int qr)
{
    S[++nodecnt]=S[now];now=nodecnt;
    S[now].sum+=Edgesum[qr]-Edgesum[ql-1];//更新当前区间
    if ((l==ql)&&(r==qr))//若正好是当前区间,则更新懒标记
    {
        S[now].lazy++;
        return;
    }
    int mid=(l+r)>>1;
    if (qr<=mid) Modify(S[now].ls,l,mid,ql,qr);
    else if (ql>=mid+1) Modify(S[now].rs,mid+1,r,ql,qr);
    else
    {
        Modify(S[now].ls,l,mid,ql,mid);Modify(S[now].rs,mid+1,r,mid+1,qr);
    }
    return;
}

ll Query(int n1,int n2,int l,int r,int ql,int qr,ll lazy)//注意这里最后一项是一路下来时累加的懒标记
{
    if ((l==ql)&&(r==qr)) return S[n2].sum-S[n1].sum+lazy*(Edgesum[r]-Edgesum[l-1]);
    int mid=(l+r)>>1;
    lazy=lazy+S[n2].lazy-S[n1].lazy;//把这一次的懒标记加上
    if (qr<=mid) return Query(S[n1].ls,S[n2].ls,l,mid,ql,qr,lazy);
    else if (ql>=mid+1) return Query(S[n1].rs,S[n2].rs,mid+1,r,ql,qr,lazy);
    else return Query(S[n1].ls,S[n2].ls,l,mid,ql,mid,lazy)+Query(S[n1].rs,S[n2].rs,mid+1,r,mid+1,qr,lazy);
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4012/Luogu3241][HNOI2015]开店(树链剖分,主席树)


HNCJ OIer 一枚