Description：

每个 $i$ 有 $k$ 个属性 $A_{i,1}\sim A_{i,k}$ ，自己也有 $k$ 个属性 $C_1\sim C_k$ ，对一个 $i$ 进行操作后会得到 $\begin{align}\sum_{j=1}^k(A_{i,j}-C_j)^2\end{align}$ 的代价，然后自己的树形变成 $i$ 的属性，对每个 $i$ 找到一个操作序列时的代价和最少。

$n=150000,k=1$ 或 $n=100000,k=2$ 数据随机。

Solution：

首先显然可以 $DP$ ，会发现上面那个式子是欧几里得距离的平方。

当 $k=1$ 时候的式子展开就会发现可以斜率优化，但是 $x,y,k$ 都不单调因此要写平衡树。

当 $k=2$ 的时候会发现没有什么办法优化，但是数据范围较小而且随机，因此可以用 $KD-Tree$ ，具体来说就是再加一个估价 $minv$ 表示子树里的 $val$ 的最小值，只有子树内最近距离 $+minv$ 比原答案更优才进入子树，时间复杂度玄学。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 100010

typedef long long ll;

namespace SPLAY

{

	struct node

	{

		int c[2],fa;

		ll x,y;

	}t[MAXN];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root = 0;

	int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

	void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

	void rotate(int x)

	{

		int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

		connect(t[x].c[fx ^ 1],y,fx);

		connect(y,x,fx ^ 1);

		connect(x,z,fy);

		return;

	}

	void splay(int x,int &des)

	{

		int fa = t[des].fa;

		while(t[x].fa != fa)

		{

			int y = t[x].fa;

			if(t[y].fa == fa){rotate(x);break;}

			if(id(x) == id(y)){rotate(y);rotate(x);}

			else {rotate(x);rotate(x);}

		}

		des = x;

		return;

	}

	int pre(int k)

	{

		if(t[k].c[0] == 0)return 0;

		k = t[k].c[0];

		while(t[k].c[1] != 0)k = t[k].c[1];

		return k;

	}

	int nxt(int k)

	{

		if(t[k].c[1] == 0)return 0;

		k = t[k].c[1];

		while(t[k].c[0] != 0)k = t[k].c[0];

		return k;

	}

	void remove(int k)

	{

		if(k == 0)return;

		splay(k,root);

		if(t[k].c[0] == 0 && t[k].c[1] == 0){t[t[k].fa].c[id(k)] = 0;return;}

		if(t[k].c[0] == 0 && t[k].c[1] != 0){connect(t[k].c[1],t[k].fa,id(k));return;}

		if(t[k].c[0] != 0 && t[k].c[1] == 0){connect(t[k].c[0],t[k].fa,id(k));return;}

		int nr = nxt(k);splay(nr,root);

		connect(t[k].c[0],nr,0);

		return;

	}

	double slope(node a,node b){return double(b.y - a.y) / double(b.x - a.x);}

	void maintain(int k)

	{

		splay(k,root);

		int pr = pre(k),nx = nxt(k);

		if(pr != 0 && nx != 0 && slope(t[pr],t[k]) >= slope(t[nx],t[k])){remove(k);return;}

		if(pr != 0)

		{

			splay(pr,t[k].c[0]);

			int ppr = pre(pr);

			while(ppr != 0 && slope(t[ppr],t[pr]) >= slope(t[pr],t[k]))

			{

				remove(pr);splay(k,root);

				splay(pr = ppr,t[k].c[0]);ppr = pre(pr);

			}

		}

		if(nx != 0)

		{

			splay(nx,t[k].c[1]);

			int nnx = nxt(nx);

			while(nnx != 0 && slope(t[nnx],t[nx]) <= slope(t[nx],t[k]))

			{

				remove(nx);splay(k,root);

				splay(nx = nnx,t[k].c[1]);nnx = nxt(nx);

			}

		}

		return;

	}

	void insert(ll x,ll y)

	{

		int k = newnode();t[k].x = x;t[k].y = y;

		if(root == 0){root = k;return;}

		int cur = root,fa = 0;

		while(true)

		{

			if(x == t[cur].x){t[cur].y = min(t[cur].y,y);maintain(cur);return;}

			int id = (x < t[cur].x ? 0 : 1);

			if(t[cur].c[id] == 0){connect(k,cur,id);maintain(k);return;}

			fa = cur;cur = t[cur].c[id];

		}

	}

	ll query(ll k)

	{

		ll ans = 0x3f3f3f3f3f3f3f3f;

		int cur = root;

		while(true)

		{

			if(cur == 0)break;

			ans = min(ans,t[cur].y - k * t[cur].x);

			if(t[cur].c[0] == 0 && t[cur].c[1] == 0){splay(cur,root);break;}

			int nx = nxt(cur),pr = pre(cur);

			if(pr == 0)

			{

				if(slope(t[cur],t[nx]) >= k)break;

				else{cur = t[cur].c[1];continue;}

			}

			if(nx == 0)

			{

				if(slope(t[cur],t[pr]) <= k)break;

				else{cur = t[cur].c[0];continue;}

			}

			if(slope(t[cur],t[pr]) >= k)cur = t[cur].c[0];

			else cur = t[cur].c[1];

		}

		return ans;

	}

}

namespace SOLVE1

{

	ll A[MAXN];

	ll f[MAXN];

	void solve()

	{

		for(int i = 1;i <= n;++i)scanf("%lld",&A[i]);

		memset(f,0x3f,sizeof(f));

		f[0] = 0;

		SPLAY::insert(0,0);

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

		{

			f[i] = SPLAY::query(2 * A[i]) + A[i] * A[i];

			SPLAY::insert(A[i],A[i] * A[i] + f[i]);

			printf("%.4lf\n",sqrt(f[i]));

		}

		return;

	}

}

namespace KDT

{

	struct node

	{

		int lc,rc;

		ll val,minv;

		int d[2],mx[2],mn[2];

	}t[MAXN];

	int ptr = 0;

	int newnode(){return ++ptr;}

	struct point

	{

		int d[2];

	}p_[MAXN],p[MAXN];

	bool operator == (point a,point b){return (a.d[0] == b.d[0] && a.d[1] == b.d[1]);}

	int tot = 0;

	void maintain(int rt)

	{

		t[rt].mn[0] = t[rt].mx[0] = t[rt].d[0];t[rt].mn[1] = t[rt].mx[1] = t[rt].d[1];

		t[rt].minv = t[rt].val;

		if(t[rt].lc != 0)

		{

			t[rt].mn[0] = min(t[rt].mn[0],t[t[rt].lc].mn[0]);t[rt].mx[0] = max(t[rt].mx[0],t[t[rt].lc].mx[0]);

			t[rt].mn[1] = min(t[rt].mn[1],t[t[rt].lc].mn[1]);t[rt].mx[1] = max(t[rt].mx[1],t[t[rt].lc].mx[1]);

			t[rt].minv = min(t[rt].minv,t[t[rt].lc].minv);

		}

		if(t[rt].rc != 0)

		{

			t[rt].mn[0] = min(t[rt].mn[0],t[t[rt].rc].mn[0]);t[rt].mx[0] = max(t[rt].mx[0],t[t[rt].rc].mx[0]);

			t[rt].mn[1] = min(t[rt].mn[1],t[t[rt].rc].mn[1]);t[rt].mx[1] = max(t[rt].mx[1],t[t[rt].rc].mx[1]);

			t[rt].minv = min(t[rt].minv,t[t[rt].rc].minv);

		}

		return;

	}

	int tp;

	bool cmp_d(point a,point b)

	{

		if(a.d[tp] == b.d[tp])return a.d[tp ^ 1] < b.d[tp ^ 1];

		else return a.d[tp] < b.d[tp];

	}

	int root;

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

	{

		if(l > r)return;

		tp = type;

		sort(p + l,p + r + 1,cmp_d);

		int mid = ((l + r) >> 1);

		rt = newnode();

		t[rt].d[0] = p[mid].d[0];t[rt].d[1] = p[mid].d[1];

		t[rt].val = 0x3f3f3f3f3f3f3f3f;

		build(t[rt].lc,l,mid - 1,type ^ 1);

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

		maintain(rt);

		return;

	}

	bool in(int rt,ll x,ll y)

	{

		return (t[rt].mn[0] <= x && x <= t[rt].mx[0] && t[rt].mn[1] <= y && y <= t[rt].mx[1]);

	}

	void insert(int rt,int x,int y,ll val)

	{

		if(t[rt].d[0] == x && t[rt].d[1] == y)

		{

			t[rt].val = min(t[rt].val,val);

			maintain(rt);

			return;

		}

		if(in(t[rt].lc,x,y))insert(t[rt].lc,x,y,val);

		if(in(t[rt].rc,x,y))insert(t[rt].rc,x,y,val);

		maintain(rt);

		return;

	}

	ll ans;

	ll sqr(int a){return 1ll * a * a;}

	ll calc(int rt,ll x,ll y)

	{

		ll xx,yy;

		if(t[rt].mn[0] <= x && x <= t[rt].mx[0])xx = x;

		else if(x < t[rt].mn[0])xx = t[rt].mn[0];

		else xx = t[rt].mx[0];

		if(t[rt].mn[1] <= y && y <= t[rt].mx[1])yy = y;

		else if(y < t[rt].mn[1])yy = t[rt].mn[1];

		else yy = t[rt].mx[1];

		return sqr(xx - x) + sqr(yy - y) + t[rt].minv;

	}

	void query(int rt,int x,int y)

	{

		if(rt == 0)return;

		ans = min(ans,sqr(t[rt].d[0] - x) + sqr(t[rt].d[1] - y) + t[rt].val);

		ll vall = calc(t[rt].lc,x,y),valr = calc(t[rt].rc,x,y);

		if(vall < valr)

		{

			if(vall < ans)query(t[rt].lc,x,y);

			if(valr < ans)query(t[rt].rc,x,y);

		}

		else

		{

			if(valr < ans)query(t[rt].rc,x,y);

			if(vall < ans)query(t[rt].lc,x,y);

		}

		return;

	}

}

namespace SOLVE2

{

	ll A[MAXN][2];

	ll f[MAXN];

	void solve()

	{

		for(int i = 1;i <= n;++i)scanf("%d%d",&A[i][0],&A[i][1]);

		for(int i = 1;i <= n;++i)KDT::p_[i].d[0] = A[i][0],KDT::p_[i].d[1] = A[i][1];

		KDT::tp = 0;

		sort(KDT::p_ + 1,KDT::p_ + 1 + n,KDT::cmp_d);

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

		{

			if(i == 1 || !(KDT::p_[i] == KDT::p_[i - 1]))KDT::p[++KDT::tot] = KDT::p_[i];

		}

		++KDT::tot;

		KDT::p[KDT::tot].d[0] = 0;KDT::p[KDT::tot].d[1] = 0;

		KDT::build(KDT::root,1,KDT::tot,0);

		memset(f,0x3f,sizeof(f));

		f[0] = 0;KDT::insert(KDT::root,0,0,0);

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

		{

			KDT::ans = 0x3f3f3f3f3f3f3f3f;

			KDT::query(KDT::root,A[i][0],A[i][1]);

			f[i] = KDT::ans;

			KDT::insert(KDT::root,A[i][0],A[i][1],f[i]);

			printf("%.4lf\n",sqrt(f[i]));

		}

		return;

	}

}

int main()

{

	scanf("%d%d",&n,&k);

	if(k == 1)SOLVE1::solve();

	else SOLVE2::solve();

	return 0;

}