首页 > 代码库 > [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]开店（树链剖分+主席树）