链接
题解
首先要发现答案要我们求这个式子：
\[ans=min\bigl((x_i-x)^2+c_i\bigr)
\]
\]
显而易见的是这种时空嫁接的关系会形成一棵树。但是我们并不能像\(NOI2014\)购票那样直接在树上维护一条链的栈，因为每个点代表的既有可能是加入一个点，又有可能是删除一个点。
考虑每个点的存在时间都是一些连续区间，所以就可以在欧拉序或者\(dfs\)序上分治了。
至于询问的方式，我们可以先把线段树上的每个节点把凸包维护出来，然后用标记永久化的思想进行查询。
如果空间利用的不当会\(MLE\)，可以考虑先用栈做凸包，然后再扔进\(vector\)里做查询用，这样可以省空间。
代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define ls tr[cnt].l
#define rs tr[cnt].r
#define N 500009
#define inf 1e16
using namespace std;
typedef long long ll;
int tot,head[N],num,val[N],n,sta[N<<1],root,dfn[N],_tag[N],m,totp;
ll ans;
ll c[N];
int pos[N];
struct edge{int n,to;}e[N];
inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}
struct seg{int l,r;}tr[N<<1];
struct node{
int x;ll y;
inline node operator +(const node &b)const{return node{1ll*x+b.x,y+b.y};}
inline node operator -(const node &b)const{return node{1ll*x-b.x,y-b.y};}
inline ll operator *(const node &b)const{return 1ll*x*b.y-y*b.x;}
inline bool operator <(const node &b)const{if(x!=b.x)return x<b.x;else return y<b.y;}
}st[N];
vector<node>vec[N<<1];
inline ll rd(){
ll x=0;char c=getchar();bool f=0;
while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?-x:x;
}
inline double getk(node x,node y){return (double)(y.y-x.y)/(y.x-x.x);}
void build(int &cnt,int l,int r){
cnt=++totp;
if(l==r)return;
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
}
inline void _query(int cnt,ll x){
if(vec[cnt].empty())return;
int l=0,r=vec[cnt].size()-2,now=r+1;
while(l<=r){
int mid=(l+r)>>1;
if(getk(vec[cnt][mid+1],vec[cnt][mid])>=x)now=mid,r=mid-1;
else l=mid+1;
}
ans=min(ans,vec[cnt][now].y-1ll*vec[cnt][now].x*x+x*x);
}
void upd(int cnt,int l,int r,int L,int R,int x){
// if(cnt==1)cout<<x<<" "<<L<<" "<<R<<endl;
if(l>=L&&r<=R){vec[cnt].push_back(node{1ll*pos[x]*2,1ll*pos[x]*pos[x]+c[x]});return;}
int mid=(l+r)>>1;
if(mid>=L)upd(ls,l,mid,L,R,x);
if(mid<R)upd(rs,mid+1,r,L,R,x);
}
void solve(int cnt,int l,int r){
sort(vec[cnt].begin(),vec[cnt].end());
int tp=0;
for(int i=0;i<vec[cnt].size();++i){
node xx=vec[cnt][i];
if(tp&&xx.x==st[tp].x)continue;
while(tp>1&&(xx-st[tp-1])*(st[tp]-st[tp-1])>=0)tp--;
st[++tp]=xx;
}
vec[cnt].clear();
for(int i=1;i<=tp;++i)vec[cnt].push_back(st[i]);
if(l==r)return;
int mid=(l+r)>>1;
solve(tr[cnt].l,l,mid);solve(tr[cnt].r,mid+1,r);
}
void query(int cnt,int l,int r,int x,int y){
_query(cnt,y);
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)query(ls,l,mid,x,y);
else query(rs,mid+1,r,x,y);
}
void work(int tim,int now,int tag){
if(tag==1){
if(val[now]>=0)sta[val[now]]=tim;
else upd(root,1,n,sta[-val[now]],tim-1,-val[now]),sta[-val[now]]=0;
}
else{
if(val[now]<0)sta[-val[now]]=tim+1;
else upd(root,1,n,sta[val[now]],tim,val[now]),sta[val[now]]=0;
}
}
void dfs(int u){
dfn[u]=++dfn[0];
work(dfn[0],u,1);
_tag[u]=dfn[0];
for(int i=head[u];i;i=e[i].n)dfs(e[i].to);
work(dfn[0],u,-1);
}
int main(){
//freopen("1.in","r",stdin);
n=rd();m=rd();c[0]=rd();
ll opt,f,id,x,y,z;
for(int i=1;i<n;++i){
opt=rd();f=rd();id=rd();add(f,i);
if(!opt){
pos[id]=rd();y=rd();z=rd();c[id]=rd();
val[i]=id;
}
else val[i]=-id;
}
build(root,1,n);
dfs(0);
for(int i=0;i<=n;++i)
if(sta[i])upd(root,1,n,sta[i],n,i);
solve(root,1,n);
int s;
for(int i=1;i<=m;++i){
s=rd();x=rd();ans=inf;
query(root,1,n,_tag[s],x);
printf("%lld\n",ans);
}
return 0;
}