Luogu P5416 [CTSC2016]时空旅行

第一次写线段树分治的题目，没想到是道这么毒的题233

首先发现题目里的\((x,y,z,c)\)就是在放屁，只有\((x,c)\)是有用的

因此我们可以把题意转化为，在某一个时间节点上，求出所有元素的

\[\min((X-x_i)^2+c_i)
\]

稍加观察会发现时间节点是成一棵树的形态的，因此对于一个星球，它存在的时间节点在树上必然是两个区间（第一次出现的子树减去第一次删除的子树，当然没删除的话就是一个区间）

因此我们利用线段树分治的思想，把这些区间扔到线段树里，考虑用线段树分治来做

然后考虑答案怎么计算，这种带平方的想想都是斜率优化或者凸包一类的东西，我们展开式子：

\[(X-x_i)^2+c_i=X^2-2Xx_i+x_i^2+c_i=b
\]

那么就有：

\[2Xx_i+b=X^2+x_i^2+c_i
\]

于是我们可以把\((x_i,X^2+x_i^2+c_i)\)看做一个决策点，现在我们需要一条斜率为\(2X\)的直线去穿过这个点，然后是的截距最小

那么我们只需要维护一个凸包，让后每次找到斜率第一个大于\(2X\)的线段，然后前面的那个点就是最优决策点

那么大致思路就来了，如果你写了可持久化平衡树维护凸包就有了时间三个\(\log\)，空间两个\(\log\)的算法

然后我们发现写动态凸包就是SB，因为插入点的顺序是由我们自己决定的，因此直接给所有星球按\(x_i\)排序插入即可，因此变成了插入一个\(\log\)，询问两个\(\log\)

然后我们发现写凸包上二分就是SB，因为询问的顺序也是由我们自己决定的，因此之间把询问的\(X\)排序后单调移动端点即可

综上，时空复杂度都是\(O(n\log n)\)的，但需要一定的常数以及特判

#include<cstdio>

#include<cctype>

#include<vector>

#include<iostream>

#include<algorithm>

#define int long long

#define RI register int

#define CI const int&

#define Tp template <typename T>

#define pb push_back

using namespace std;

const int N=500005,INF=1e18;

struct edge

{

	int to,nxt;

}e[N<<1]; int n,m,head[N],cnt,c[N],vx[N],id[N],a[N],opt,x,y,z,u,v;

struct ques

{

	int pos,val,id;

	friend inline bool operator < (const ques& A,const ques& B)

	{

		return A.val<B.val;

	}

}q[N]; int dfn[N],idx,ans[N]; vector <int> L[N],R[N];

class FileInputOutput

{

	private:

		static const int S=1<<18;

		#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)

		#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))

		char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[25];

	public:

		inline FileInputOutput() { Ftop=Fout; Fend=Fout+S; }

		Tp inline void read(T& x)

		{

			x=0; char ch; int flag=1; while (!isdigit(ch=tc())) if (ch=='-') flag=-1;

			while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag;

		}

		Tp inline void write(T x)

		{

			RI ptop=0; while (pt[++ptop]=x%10,x/=10);

			while (ptop) pc(pt[ptop--]+48); pc('\n');

		}

		inline void flush(void)

		{

			fwrite(Fout,1,Ftop-Fout,stdout);

		}

		#undef tc

		#undef pc

}F;

inline void addedge(CI x,CI y)

{

	e[++cnt]=(edge){y,head[x]}; head[x]=cnt;

	e[++cnt]=(edge){x,head[y]}; head[y]=cnt;

}

#define to e[i].to

inline void DFS(CI now=1,CI fa=0)

{

	dfn[now]=++idx; if (id[now]>0) L[id[now]].pb(idx); if (id[now]<0) R[-id[now]].pb(idx-1);

	for (RI i=head[now];i;i=e[i].nxt) if (to!=fa) DFS(to,now);

	if (id[now]>0) R[id[now]].pb(idx); if (id[now]<0) L[-id[now]].pb(idx+1);

}

#undef to

inline bool cmpid(CI x,CI y)

{

	return vx[x]<vx[y];

}

class Segment_Tree

{

	private:

		struct segment

		{

			int head,tail; vector <int> pnt;

		}node[3*N+10];

		#define H(x) node[x].head

		#define T(x) node[x].tail

		#define S(x) node[x].pnt.size()

		#define P(x,y) node[x].pnt[y]

		#define TN CI now=1,CI l=1,CI r=n

		#define LS now<<1,l,mid

		#define RS now<<1|1,mid+1,r

		inline int sqr(CI x)

		{

			return x*x;

		}

		inline long double slope(CI x,CI y)

		{

			return 1.0*(sqr(vx[x])+c[x]-sqr(vx[y])-c[y])/(vx[x]-vx[y]);

		}

	public:

		inline void build(TN)

		{

			T(now)=-1; if (l==r) return; int mid=l+r>>1; build(LS); build(RS);

		}

		inline void insert(CI beg,CI end,CI id,TN)

		{

			if (beg==l&&r==end)

			{

				if (S(now)<=T(now)+5) node[now].pnt.resize(T(now)+5);

				if (H(now)<=T(now)&&vx[P(now,T(now))]==vx[id])

				{ if (c[P(now,T(now))]<=c[id]) return; --T(now); }

				while (H(now)<T(now)&&slope(P(now,T(now)),id)<slope(P(now,T(now)-1),P(now,T(now))))

				--T(now); P(now,T(now)+1)=id; ++T(now); return;

			}

			int mid=l+r>>1; if (end<=mid) insert(beg,end,id,LS);

			else if (beg>mid) insert(beg,end,id,RS); else

			insert(beg,mid,id,LS),insert(mid+1,end,id,RS);

		}

		inline int query(CI pos,CI val,TN)

		{

			while (H(now)<T(now)&&slope(P(now,H(now)),P(now,H(now)+1))<=2.0*val) ++H(now);

			int ret=INF; if (H(now)<=T(now)&&S(now)) ret=sqr(val-vx[P(now,H(now))])+c[P(now,H(now))];

			if (l==r) return ret; int mid=l+r>>1; return min(ret,pos<=mid?query(pos,val,LS):query(pos,val,RS));

		}

		#undef H

		#undef T

		#undef S

		#undef P

		#undef TN

		#undef LS

		#undef RS

}SEG;

signed main()

{

	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

	RI i,j; for (F.read(n),F.read(m),F.read(c[0]),i=1;i<n;++i)

	{

		F.read(opt); F.read(u); F.read(v); if (!opt)

		F.read(vx[v]),F.read(y),F.read(z),F.read(c[v]),id[i]=v,addedge(u,i);

		else id[i]=-v,addedge(u,i);

	}

	for (DFS(),SEG.build(),i=1;i<=n;++i) a[i]=i; sort(a+1,a+n+1,cmpid);

	for (SEG.insert(1,n,0),i=1;i<=n;++i)

	for (y=a[i],z=L[y].size(),j=0;j<z;++j)

	if (L[y][j]<=R[y][j]) SEG.insert(L[y][j],R[y][j],y);

	for (i=1;i<=m;++i) F.read(q[i].pos),F.read(q[i].val),q[i].id=i;

	for (sort(q+1,q+m+1),i=1;i<=m;++i)

	ans[q[i].id]=q[i].pos?SEG.query(dfn[q[i].pos],q[i].val):q[i].val*q[i].val+c[0];

	for (i=1;i<=m;++i) F.write(ans[i]); return F.flush(),0;

}

巴特西

Luogu P5416 [CTSC2016]时空旅行

最新文章

热门文章