HNOI2015 Day2 T2,一道动态点分治板子题。
题目链接:HNOI2015 Day2 T2、Luogu P3241、LOJ 2116、BZOJ 4012。
题目
风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。
这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 \(n\) 个地方,编号为 \(1\) 到 \(n\) 被 \(n-1\) 条带权的边连接起来。每个地方都住着一个妖怪,其中第 \(i\) 个地方的妖怪年龄是 \(x _ i\)。
妖怪都是些比较喜欢安静的家伙,所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 \(3\)。妖怪和人一样,兴趣点随着年龄的变化自然就会变化,比如我们的 \(18\) 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现,基本上妖怪的兴趣只跟年龄有关,所以幽香打算选择一个地方 \(u\)(\(u\) 为编号),然后在 \(u\) 开一家面向年龄在 \(L\) 到 \(R\) 之间(即年龄大于等于 \(L\) 小于等于 \(R\))的妖怪的店。
也有可能 \(u\) 这个地方离这些妖怪比较远,于是幽香就想要知道所有年龄在 \(L\) 到 \(R\) 之间的妖怪,到点 \(u\) 的距离的和是多少(妖怪到 \(u\) 的距离是该妖怪所在地方到 \(u\) 的路径上的边的权之和),幽香把这个称为这个开店方案的方便值。
幽香她们还没有决定要把店开在哪里,八云紫倒是准备了很多方案,于是幽香想要知道,对于每个方案,方便值是多少呢。
数据范围
变量 | 数据范围 |
\(n\) | \(\leq 1.5\times 10^5\) |
\(Q\) | \(\leq 2\times 10^5\) |
\(A\) | \(\leq 10^9\) |
时空限制
题目编号 | 时间限制 | 空间限制 |
HNOI2015 Day2 T2 | \(6\texttt{s}\) | \(512\texttt{MiB}\) |
Luogu P3241 | \(6\texttt{s}\) | \(500\texttt{MiB}\) |
LOJ 2116 | \(6\texttt{s}\) | \(512\texttt{MiB}\) |
BZOJ 4012 | \(6\texttt{s}\) | \(512\texttt{MiB}\) |
题解
思路
动态点分治板子题。主要是卡常数。
- 快读必须加上;
- 存图用 \(\texttt{vector}\),这是 cache friendly 的。
- 尽量少调用函数,函数传参,参数不变时改成全局变量。
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=1.5e5+5; const int MAXQ=2e5+5; const int inf=0x3f3f3f3f; int n,Q,A; int x[MAXN]; namespace Tree{ struct Edge{ int to,w; inline Edge(reg int to=0,reg int w=0):to(to),w(w){ return; } }; vector<Edge> G[MAXN]; inline void Add_Edge(reg int u,reg int v,reg int len){ G[u].push_back(Edge(v,len)); return; } struct Nodef{ int id,fa,dis; inline Nodef(reg int id=0,reg int fa=0,reg int dis=0):id(id),fa(fa),dis(dis){ return; } }; struct Nodes{ int age,cnt; ll dis; inline Nodes(reg int age=0,reg int cnt=0,reg ll dis=0):age(age),cnt(cnt),dis(dis){ return; } inline bool operator<(const Nodes& a)const{ return age<a.age; } }; vector<Nodef> fa[MAXN]; vector<Nodes> son[MAXN][3]; bitset<MAXN> del; int root,MaxPart; int size[MAXN]; int _tot; inline void DFS1(reg int u,reg int father){ size[u]=1; int Max=0; for(auto E:G[u]){ reg int v=E.to; if(v!=father&&!del[v]){ DFS1(v,u); size[u]+=size[v]; Max=max(Max,size[v]); } } Max=max(Max,_tot-size[u]); if(Max<MaxPart) root=u,MaxPart=Max; return; } int dis[MAXN]; int _id; inline void DFS2(reg int u,reg int father){ fa[u].push_back(Nodef(_id,root,dis[u])); son[root][_id].push_back(Nodes(x[u],1,dis[u])); for(auto E:G[u]){ reg int v=E.to,w=E.w; if(v!=father&&!del[v]){ dis[v]=dis[u]+w; DFS2(v,u); } } return; } inline void solve(reg int u,reg int tot){ if(tot==1){ del[u]=true; fa[u].push_back(Nodef(-1,u,0)); return; } MaxPart=inf; _tot=tot; DFS1(u,0); del[root]=true; fa[root].push_back(Nodef(-1,root,0)); reg int id=0; for(auto E:G[root]){ reg int v=E.to,w=E.w; if(del[v]) continue; dis[v]=w; _id=id; DFS2(v,0); son[root][id].push_back(Nodes(inf,0,0)); sort(son[root][id].begin(),son[root][id].end()); for(reg int j=son[root][id].size()-2;j>=0;--j){ son[root][id][j].cnt+=son[root][id][j+1].cnt; son[root][id][j].dis+=son[root][id][j+1].dis; } ++id; } for(auto E:G[root]){ reg int v=E.to; if(!del[v]) solve(v,size[v]); } return; } inline ll query(reg int l,reg int r,reg int u){ reg ll res=0; static vector<Nodes>::iterator L,R; for(reg int i=fa[u].size()-1;i>=0;--i){ reg int f=fa[u][i].fa; for(reg int id=0;id<3;++id){ if(id==fa[u][i].id||son[f][id].empty()) continue; L=lower_bound(son[f][id].begin(),son[f][id].end(),Nodes(l,0,0)); R=upper_bound(son[f][id].begin(),son[f][id].end(),Nodes(r,0,0)); res+=1ll*fa[u][i].dis*(L->cnt-R->cnt)+L->dis-R->dis; } if(l<=x[f]&&x[f]<=r) res+=fa[u][i].dis; } return res; } } int main(void){ n=read(),Q=read(),A=read(); for(reg int i=1;i<=n;++i) x[i]=read(); for(reg int i=1;i<n;++i){ static int a,b,c; a=read(),b=read(),c=read(); Tree::Add_Edge(a,b,c); Tree::Add_Edge(b,a,c); } Tree::solve(1,n); reg ll lastans=0; for(reg int i=1;i<=Q;++i){ static int u; static ll a,b; u=read(),a=read(),b=read(); a=(a+lastans)%A,b=(b+lastans)%A; if(a>b) swap(a,b); printf("%lld\n",lastans=Tree::query(a,b,u)); } return 0; }
近期评论