首页 > 代码库 > [BZOJ 4012][HNOI2015]开店(树链剖分+主席树)

[BZOJ 4012][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 的路径上的边的权之和) ,幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里,八云紫倒是准备了很多方案,于是幽香想要知道,对于每个方案,方便值是多少呢。

Solution

和LCA那道是有一些相似的,没有A那道题的可以先去看一下√

本来是一道动态树分治?听说可以用树剖就很开心地去码了,结果代码能力太弱各种WAQAQ

最后还是抄了神犇代码

将年龄离散化以后按顺序加入,每次把这个点到root的边加进主席树

点u、v路径上的边权之和即 u到root的边权+v到root的边权-lca(u,v)到root的边权*2

则年龄在L到R间的妖怪到u的边权之和即 ∑{dis[v]+dis[lca(u,v)]*2}+dis[u]*妖怪个数(L<=v<=R)

dis[lca(u,v)]通过在主席树(L~R间的)上查询u到根的边权和得出,其余的可以用前缀和维护

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define N 150005#define Q 200005using namespace std;typedef long long LL;int n,q,A,x[N],y[N],head[N],cnt=0;int father[N],deep[N],pos[N],top[N],siz[N],maxv[N],sz=0;int rt[N],ls[N*120],rs[N*120],tot=0;LL sum[N*120],lazy[N*120],dis[N],d[N],w[N],p1[N],p2[N];LL read(){    LL x=0,f=1;char c=getchar();    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}struct Node1{    int next,to,w;}Edges[N*2];struct Node2{    int age,id;    Node2(int age=0,int id=0):age(age),id(id){}    bool operator < (const Node2& t) const    {return age<t.age;}}data[N];void addedge(int u,int v,int w){    Edges[++cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v;    Edges[cnt].w=w;}void dfs1(int u){    siz[u]=1;    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(v==father[u])continue;        father[v]=u;        deep[v]=deep[u]+1,d[v]=Edges[i].w,dis[v]=dis[u]+Edges[i].w;        dfs1(v);siz[u]+=siz[v];        if(!maxv[u]||siz[v]>siz[maxv[u]])maxv[u]=v;    }}void dfs2(int u,int t){    top[u]=t;    ++sz,pos[u]=sz;    w[sz]=w[sz-1]+d[u],p1[x[u]]++,p2[x[u]]+=dis[u];    if(maxv[u])dfs2(maxv[u],t);    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(v==maxv[u]||v==father[u])continue;        dfs2(v,v);    }}void insert(int &idx,int last,int l,int r,int L,int R){    ++tot,idx=tot;    sum[idx]=sum[last],lazy[idx]=lazy[last],ls[idx]=ls[last],rs[idx]=rs[last];    if(L==l&&R==r){lazy[idx]++;sum[idx]+=w[r]-w[l-1];return;}    int mid=(l+r)>>1;    if(R<=mid)insert(ls[idx],ls[last],l,mid,L,R);    else if(L>mid)insert(rs[idx],rs[last],mid+1,r,L,R);    else insert(ls[idx],ls[last],l,mid,L,mid),insert(rs[idx],rs[last],mid+1,r,mid+1,R);    sum[idx]=sum[ls[idx]]+sum[rs[idx]]+lazy[idx]*(w[r]-w[l-1]);}LL query(int s,int t,int l,int r,int L,int R,int tag){    if(L==l&&R==r)return sum[s]-sum[t]+1LL*tag*(w[r]-w[l-1]);    int mid=(l+r)>>1;tag+=lazy[s]-lazy[t];    if(R<=mid)return query(ls[s],ls[t],l,mid,L,R,tag);    else if(L>mid)return query(rs[s],rs[t],mid+1,r,L,R,tag);    else return query(ls[s],ls[t],l,mid,L,mid,tag)+query(rs[s],rs[t],mid+1,r,mid+1,R,tag);}void add(int i,int x){    while(x)    {        insert(rt[data[i].age],rt[data[i].age],1,sz,pos[top[x]],pos[x]);        x=father[top[x]];    }}LL ask(int l,int r,int u){    LL res=0;    while(u)    {        res+=query(rt[r],rt[l-1],1,sz,pos[top[u]],pos[u],0);        u=father[top[u]];    }    return res;}int main(){    memset(head,-1,sizeof(head));    n=read(),q=read(),A=read();    for(int i=1;i<=n;i++)y[i]=x[i]=read();    sort(y+1,y+1+n);    int t=unique(y+1,y+1+n)-y-1;    for(int i=1;i<=n;i++)x[i]=lower_bound(y+1,y+1+t,x[i])-y;    for(int i=1;i<n;i++)    {        int a=read(),b=read(),c=read();        addedge(a,b,c),addedge(b,a,c);    }    dfs1(1);dfs2(1,1);    for(int i=1;i<=n;i++)data[i]=Node2(x[i],i);    sort(data+1,data+1+n);    for(int i=1;i<=n;i++)    {        if(!rt[data[i].age])        rt[data[i].age]=rt[data[i].age-1];        add(i,data[i].id);    }    for(int i=1;i<=t;i++)p1[i]+=p1[i-1],p2[i]+=p2[i-1];    LL last=0;    for(int i=1;i<=q;i++)    {        LL u=read(),a=read(),b=read();        int l=min((a+last)%A,(b+last)%A),r=max((a+last)%A,(b+last)%A);        l=lower_bound(y+1,y+1+t,l)-y,r=upper_bound(y+1,y+1+t,r)-y-1;        if(l>r||l>t||r<1){last=0;printf("0\n");continue;}        last=dis[u]*(p1[r]-p1[l-1])+p2[r]-p2[l-1]-2*ask(l,r,u);        printf("%lld\n",last);    }    return 0;}

 

---恢复内容结束---

[BZOJ 4012][HNOI2015]开店(树链剖分+主席树)