首先，发现 $y,z$ 完全没用，题目的大意就是说每个点有一个集合，集合中的每个元素为 $(x_i,c_i)$ ，然后每一次询问一个点，再给出一个 $X$，需要你求出这个点的集合的所有元素中，$(x_i-X)^2+c_i$ 的最小值，输出这个最小值。
展开一下 $(x_i-X)^2+c_i$ ，会发现其实就等于 $X^2-2x_iX+x_i^2+c_i$ ，后面的那一坨显然就是一个一次函数。
很显然的想法就是每个点一棵线段树维护一下下凸包，这个很简单，就是直接爆炸。
然后会发现一个性质，按照题目来的话，同时拥有 $s$ 星球的节点应该是 $dfn$ 序列上的连续的区间，这样就只需要用线段树以 $dfn$ 序列的位置为下标维护信息。
然后就是将处理出这些区间操作。
void dfs(int u,int fa) {
size[u]=1,dfn[u]=++dfn[0];
if(!type[u]) /*新增一个，也就是这里会作为一个区间操作的左端点*/
Dfn_L[change_id[u]].push_back(dfn[u]);
else /*删掉一个，也就是上一个访问的节点会作为这个区间操作的右端点*/
Dfn_R[change_id[u]].push_back(dfn[u]-1);
for(int i=head[u],v;i;i=G[i].nxt)
if((v=G[i].to)!=fa) dfs(v,u),size[u]+=size[v];
if(!type[u]) /*很显然如果这里新增一个的话，其贡献范围最多就是其子树*/
Dfn_R[change_id[u]].push_back(dfn[u]+size[u]-1);
else /*为什么这里可以删除，一定是因为其祖先节点拥有该星球，但是这个操作对
u 的子树不能有贡献，那么直接跳到下一个访问的节点即可。*/
Dfn_L[change_id[u]].push_back(dfn[u]+size[u]);
}
然后具体怎么实现？
好像是标记永久化？每一次在 $l,r$ 区间中新增一个函数 $x$ ，询问的时候将线段树一条链上的所有答案取 $\min$ ，也就是说这个函数不下传。
挺好打的。
Code：
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define freopen(x) {freopen(x".in","r",stdin),freopen(x".out","w",stdout);}
const int N=5e5+2;
const ll inf=2e17+2;
bool type[N];
ll ans[N];
int n,m,cnt,tot,dfn[N],size[N],change_id[N],head[N];
vector <int> Dfn_L[N],Dfn_R[N];
struct Ball {int x;ll c;} B[N];
struct Edge {int nxt,to;} G[N<<1];
struct Change {int l,r;ll k,b;} C[N];
struct Query {int id,node;ll X;} Q[N];
inline void add(int u,int v) {G[++cnt]=(Edge){head[u],v},head[u]=cnt;}
template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}
void dfs(int u,int fa) {
size[u]=1,dfn[u]=++dfn[0];
if(!type[u]) Dfn_L[change_id[u]].push_back(dfn[u]);
else Dfn_R[change_id[u]].push_back(dfn[u]-1);
for(int i=head[u],v;i;i=G[i].nxt)
if((v=G[i].to)!=fa) dfs(v,u),size[u]+=size[v];
if(!type[u]) Dfn_R[change_id[u]].push_back(dfn[u]+size[u]-1);
else Dfn_L[change_id[u]].push_back(dfn[u]+size[u]);
}
namespace Segment_Tree {
#define mid ((l+r)>>1)
int now[N<<2];
vector <int> t[N<<2];
inline double slope(int x,int y) {
if(C[x].k==C[y].k) return C[x].b>C[y].b?-inf:inf;
else return 1.0*(C[x].b-C[y].b)/(C[x].k-C[y].k);
}
void insert(int x,int l,int r,int L,int R,int id) {
if(L<=l&&r<=R) {
int I=t[x].size()-1;
while(I>0&&slope(t[x][I-1],t[x][I])>slope(t[x][I],id)) --I,t[x].pop_back();
t[x].push_back(id);return;
}
if(L<=mid) insert(x<<1,l,mid,L,R,id);
if(R>mid) insert(x<<1|1,mid+1,r,L,R,id);
}
ll query(int x,int l,int r,int pos,ll X) {
ll res=inf;
int&I=now[x];int S=t[x].size()-1;
while(I<S&&slope(t[x][I],t[x][I+1])<X) ++I;
if(I<=S) res=C[t[x][I]].b-C[t[x][I]].k*X+X*X;
if(l==r) return res;
return min(res,pos<=mid?query(x<<1,l,mid,pos,X):query(x<<1|1,mid+1,r,pos,X));
}
}using namespace Segment_Tree;
inline bool cmp_C_slope(Change a,Change b) {return a.k<b.k;}
inline bool cmp_Q_slope(Query a,Query b) {return a.X<b.X;}
int main() {
freopen("2987");
IN(n),IN(m),IN(B[1].c),change_id[1]=1;
for(int i=2;i<=n;++i) {
int op,fr,id,x,y,z;ll c;
IN(op),IN(fr),IN(id),++fr,++id,add(i,fr),add(fr,i);
change_id[i]=id;
if(op==0) IN(x),IN(y),IN(z),IN(c),B[id]=(Ball){x,c};
else type[i]=1;
}
dfs(1,0);
for(int i=1;i<=n;++i)
for(int j=0;j<Dfn_L[i].size();++j)
C[++tot]=(Change){Dfn_L[i][j],Dfn_R[i][j],2ll*B[i].x,1ll*B[i].x*B[i].x+B[i].c};
sort(C+1,C+1+tot,cmp_C_slope);
for(int i=1;i<=m;++i) IN(Q[i].node),IN(Q[i].X),Q[i].id=i,++Q[i].node;
sort(Q+1,Q+1+m,cmp_Q_slope);
for(int i=1;i<=tot;++i) insert(1,1,n,C[i].l,C[i].r,i);
for(int i=1;i<=m;++i) ans[Q[i].id]=query(1,1,n,dfn[Q[i].node],Q[i].X);
for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
return 0;
}
0 条评论