【CTSC2016】时空旅行

  • 本文为博主原创，未经许可不得转载

这个题面写的好中文啊，我看了半天才看懂

首先我们发现$ans=x_{0}^{2}+x_{i}^{2}-2x_{i}x_{0}$

设$f(x_0)=-2x_i x_0+x_{i}^{2}+c_i$

我们要求$f(x_0)$的最小值，然后我们发现这东西是一条直线

所以对于每个时空，我们对该时空的所有直线维护一个凸包即可

但是暴力维护的复杂度太高，同时我们发现一个结点的直线只对它的子树有贡献

所以我们可以使用标记永久化的线段树

按照dfs序建线段树，事先离线处理出没有贡献的子树，修改时忽略该子树即可

这样每次查询时记录从根到叶子结点的答案就行了

注意查询时在凸包上二分的话复杂度是$O(nlog^{2}n)$的

实际上我们可以先把询问按照$x$排序，维护凸包上的单调性，就可以做到$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 500100
#define INF 1e18
using namespace std;
typedef long long ll;
struct node1{int x;ll c;}planet[MAXN];
struct node2{int y,next;}e[MAXN];
struct node3{int s,x,id;}Q[MAXN];
struct node4{int k;ll b;ll cal(int x){return (ll)k*x+b;}};
int n,m,len,dfs_clock,Link[MAXN],temp[MAXN<<2],L[MAXN],R[MAXN],belong[MAXN];
ll c0,ans[MAXN];
vector<int>del[MAXN];
vector<node4>st[MAXN<<2];
inline ll read(){
	ll x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
bool cmp1(int a,int b){return planet[a].x<planet[b].x;}
bool cmp2(int x,int y){return L[x]<L[y];}
bool cmp3(node3 a,node3 b){return a.x<b.x;}
void insert(int x,int y){e[++len]=(node2){y,Link[x]};Link[x]=len;}
void dfs(int x){L[x]=++dfs_clock;for(int i=Link[x];i;i=e[i].next)dfs(e[i].y);R[x]=dfs_clock;}
bool judge(node4 a,node4 b,node4 c){
	if(b.k==c.k) return c.b<=b.b;
	return (b.b-a.b)*(a.k-c.k)>(c.b-a.b)*(a.k-b.k);
}
void updata(int p,int l,int r,int x,int y,node4 Line){
	if(x>r||y<l)  return;
	if(x<=l&&y>=r){
		while(st[p].size()>1&&judge(st[p][st[p].size()-2],st[p].back(),Line)) st[p].pop_back();
		st[p].push_back(Line);  return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) updata(p<<1,l,mid,x,y,Line);
	if(y>mid) updata(p<<1|1,mid+1,r,x,y,Line);
}
ll query(int p,int l,int r,int pos,int x){
	while(temp[p]+1<st[p].size()&&st[p][temp[p]].cal(x)>st[p][temp[p]+1].cal(x)) ++temp[p];
	ll ans=st[p].size()?st[p][temp[p]].cal(x):INF;
	if(l==r)  return ans;
	int mid=(l+r)>>1;
	if(pos<=mid) return min(ans,query(p<<1,l,mid,pos,x));
	else return min(ans,query(p<<1|1,mid+1,r,pos,x));
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  c0=read();
	for(int i=1;i<n;++i){
		int opt=read(),fr=read(),id=read();
		temp[i]=i;  insert(fr,i);
		if(!opt){
			int x=read(),y=read(),z=read();ll c=read();
			belong[id]=i;  planet[id]=(node1){x,c};
		}
		else del[id].push_back(i);
	}
	dfs(0);  sort(temp+1,temp+n,cmp1);
	for(int i=1;i<n;++i)if(belong[temp[i]]){
		int now=temp[i],pos=belong[now];
		node4 Line=(node4){-2*planet[now].x,planet[now].c+(ll)planet[now].x*planet[now].x};
		if(!del[now].size()) updata(1,1,n,L[pos],R[pos],Line);
		else{
			sort(del[now].begin(),del[now].end(),cmp2);
			updata(1,1,n,L[pos],L[del[now][0]]-1,Line);
			updata(1,1,n,R[del[now].back()]+1,R[pos],Line);
			for(int j=0;j<del[now].size()-1;++j)
				if(R[del[now][j]]+1<L[del[now][j+1]]) updata(1,1,n,R[del[now][j]]+1,L[del[now][j+1]]-1,Line);
		}
	}
	for(int i=1;i<=m;++i){int s=read(),x=read();Q[i]=(node3){s,x,i};}
	sort(Q+1,Q+m+1,cmp3);memset(temp,0,sizeof(temp));
	for(int i=1;i<=m;++i)ans[Q[i].id]=min(c0+(ll)Q[i].x*Q[i].x,(ll)Q[i].x*Q[i].x+query(1,1,n,L[Q[i].s],Q[i].x));
	for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
	return 0;
}

本文标题:【CTSC2016】时空旅行

文章作者:chty

发布时间:2017年04月26日 - 15时36分

最后更新:2018年06月08日 - 18时45分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,