Description：

你需要维护若干个版本的集合，每个集合元素是 $(x,v)$ ，每次可以扩展一个版本，扩展内容为加一个新元素或删除一个已有元素，每次询问一个 $x_0$ ，要你在给定版本 $i$ 的集合中找出 $(x_i,v_i)$ 使得 $(x_i−x_0)^2+v_i$ 最小。

$1\leqslant n\leqslant 10^6$

Solution：

首先化式子： $$ f_i=(x_i-x_0)^2+v_i=x_i^2-2x_ix_0+x_0^2+v_i $$ 显然是一个一次函数的形式（把 $x_0$ 看成自变量， $f_i$ 看成因变量），那么我们就可以维护凸包来解决他，类似膜法那道题的做法，我们可以用线段树分治，这样就不用删除凸包中的点了，然后每次就在这个点到线段树根的所有凸包上查询即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

typedef long long ll;

inline ll rd()

{

	register ll res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

#define MAXN 500010

struct planet

{

	ll x,c;

}p[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

struct option

{

	int tp,pos,id;

}o[MAXN];

int tot = 0;

int dfn[MAXN],rnk[MAXN],siz[MAXN];

void dfs(int k)

{

	dfn[++dfn[0]] = k;rnk[k] = dfn[0];

	siz[k] = 1;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		dfs(e[i].to);

		siz[k] += siz[e[i].to];

	}

	return;

}

struct node

{

	int lc,rc;

	vector< pair<ll,ll> > v;

}t[MAXN << 1];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

vector<int> s[MAXN];

bool cmp_pos(int a,int b){return abs(a) < abs(b);}

int diff[MAXN];

void add(int rt,int L,int R,pair<ll,ll> p,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].v.push_back(p);

		return;

	}

	if(L <= mid)add(t[rt].lc,L,R,p,l,mid);

	if(R > mid)add(t[rt].rc,L,R,p,mid + 1,r);

	return;

}

inline double slope(pair<ll,ll> a,pair<ll,ll> b)

{

	return double(a.second - b.second) / double(a.first - b.first);

}

pair<ll,ll> stack[MAXN];

int top = 0;

#define fi first

#define se second

inline void calc(int rt,int l,int r)

{

	sort(t[rt].v.begin(),t[rt].v.end());

	int p = -1,s = t[rt].v.size();

	for(int i = 0;i < s;++i)

	{

		if(i == 0 || t[rt].v[i].fi != t[rt].v[p].fi)t[rt].v[++p] = t[rt].v[i];

		else if(t[rt].v[i].fi == t[rt].v[p].fi)t[rt].v[p].se = min(t[rt].v[p].se,t[rt].v[i].se);

	}

	t[rt].v.resize(p + 1);

	top = 0;

	for(register vector< pair<ll,ll> >::iterator it = t[rt].v.begin();it != t[rt].v.end();++it)

	{

		while(top >= 2 && slope(stack[top - 1],stack[top]) >= slope(stack[top],*it))--top;

		stack[++top] = *it;

	}

	t[rt].v.clear();

	for(register int i = 1;i <= top;++i)t[rt].v.push_back(stack[i]);

	t[rt].v.push_back(make_pair(stack[top].first + 1,0x3f3f3f3f3f3f3f3f));

	if(l == r)return;

	calc(t[rt].lc,l,mid);

	calc(t[rt].rc,mid + 1,r);

	return;

}

inline ll query(int rt,ll x)

{

	register int l = 0,r = t[rt].v.size() - 2,mi;

	register ll res = 0x3f3f3f3f3f3f3f3f;

	while(l < r)

	{

		mi = ((l + r) >> 1);

		if(slope(t[rt].v[mi],t[rt].v[mi + 1]) >= 2 * x)r = mid;

		else l = mid + 1;

	}

	return 1ll * x * x - 2 * t[rt].v[l].first * x + t[rt].v[l].second;

}

ll query(int rt,int p,ll x,int l,int r)

{

	register ll res = query(rt,x);

	if(l == r)return res;

	if(p <= mid)res = min(res,query(t[rt].lc,p,x,l,mid));

	else res = min(res,query(t[rt].rc,p,x,mid + 1,r));

	return res;

}

int main()

{

	scanf("%d%d%lld",&n,&m,&p[1].c);

	p[1].x = 0;

	register int tp,fr,id;

	ll x,y,z,c;

	o[++tot] = (option){0,1,1};

	for(register int i = 2;i <= n;++i)

	{

		tp = rd();

		if(tp == 0)

		{

			fr = rd();id = rd();x = rd();y = rd();z = rd();c = rd();

			++fr;++id;add(fr,i);

			o[++tot] = (option){0,i,id};

			p[id].x = x;p[id].c = c;

		}

		if(tp == 1)

		{

			fr = rd();id = rd();

			++fr;++id;add(fr,i);

			o[++tot] = (option){1,i,id};

		}

	}

	dfs(1);

	build(root,1,n);

	for(register int i = 1;i <= tot;++i)

	{

		if(o[i].tp == 0)

		{

			register int p = o[i].pos;

			register int id = o[i].id;

			s[id].push_back(rnk[p]);

			s[id].push_back(-(rnk[p] + siz[p]));

		}

		else

		{

			register int p = o[i].pos;

			register int id = o[i].id;

			s[id].push_back(-rnk[p]);

			s[id].push_back(rnk[p] + siz[p]);

		}

	}

	for(register int i = 1;i <= n;++i)

	{

		if(s[i].size() == 0)continue;

		sort(s[i].begin(),s[i].end(),cmp_pos);

		for(register vector<int>::iterator it = s[i].begin();it != s[i].end();++it)

			diff[abs(*it)] += (*it > 0 ? 1 : -1);

		register int last = 0;

		for(register vector<int>::iterator it = s[i].begin();it != s[i].end();++it)

		{

			if(diff[abs(*it)] == 0)continue;

			if(*it > 0)last = *it,diff[*it] = 0;

			else add(root,last,abs(*it) - 1,make_pair(p[i].x,p[i].x * p[i].x + p[i].c),1,n),diff[abs(*it)] = 0;

		}

	}

	calc(root,1,n);

	register int pos;

	register ll x_0;

	for(register int i = 1;i <= m;++i)

	{

		pos = rd();x_0 = rd();++pos;

		pos = rnk[pos];

		printf("%lld\n",query(root,pos,x_0,1,n));

	}

	return 0;

}