[bzoj3672][线段树][可持久化凸壳]购票

Description

今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。
全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v，我们给出了它在这棵树上的父亲城市 fv 以及到父亲城市道路的长度
sv。从城市 v 前往SZ市的方法为：选择城市 v 的一个祖先 a，支付购票的费用，乘坐交通工具到达 a。再选择城市 a 的一个祖先
b，支付费用并到达 b。以此类推，直至到达SZ市。对于任意一个城市 v，我们会给出一个交通工具的距离限制 lv。对于城市 v 的祖先
a，只有当它们之间所有道路的总长度不超过 lv 时，从城市 v 才可以通过一次购票到达城市 a，否则不能通过一次购票到达。对于每个城市
v，我们还会给出两个非负整数 pv,qv 作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d，那么从城市 v 到城市 a
购买的票价为 dpv+qv。
每个城市的OIer都希望自己到达SZ市时，用于购票的总资金最少。你的任务就是，告诉每个城市的OIer他们所花的最少资金是多少。

Input

第 1 行包含2个非负整数 n,t，分别表示城市的个数和数据类型（其意义将在后面提到）。输入文件的第 2 到 n
行，每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v，分别表示城市 v
的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。请注意：输入不包含编号为 1 的SZ市，第 2 行到第 n 行分别描述的是城市
2 到城市 n。

Output

输出包含 n-1 行，每行包含一个整数。其中第 v 行表示从城市 v+1 出发，到达SZ市最少的购票费用。同样请注意：输出不包含编号为 1
的SZ市。

Sample Input

7 3

1 2 20 0 3

1 5 10 100 5

2 4 10 10 10

2 9 1 100 10

3 5 20 100 10

4 4 20 0 10

Sample Output

40

150

70

149

300

150

HINT

对于所有测试数据，保证 0≤pv≤106，0≤qv≤1012，1≤fv<v；保证
0<sv≤lv≤2×1011，且任意城市到SZ市的总路程长度不超过 2×1011。

输入的 t 表示数据类型，0≤t<4，其中：

当 t=0 或 2 时，对输入的所有城市 v，都有 fv=v-1，即所有城市构成一个以SZ市为终点的链；

当 t=0 或 1 时，对输入的所有城市 v，都有 lv=2×1011，即没有移动的距离限制，每个城市都能到达它的所有祖先；

当 t=3 时，数据没有特殊性质。

n=2×10^5

题解

设一个 $f[i]$ 表示 $i$ 到根的最少钱数
显然有一个dp
$f[i]=f[j]+(sum[i]-sum[j])*p[i]+q[i]$
式子一拆
$f[i]=-sum[j]*p[i]+f[j]+sum[i]*p[i]+q[i]$
后面是常数，相当于对于每个 $j$ 维护一条 $-sum[j]*x+f[j]$ 的直线，支持询问在 $x$ 坐标最小值
斜率单调直接单调栈
只考虑在序列上的情况，这个可以维护一个单调栈
拓展到树上
发现对于任意一个点，能影响他的依然是一个序列
我们考虑用线段树维护区间的单调栈
相当于维护 $[1,dep],[1,dep/2],1[dep/4]...$ 这些区间的单调栈
询问的时候找到这些区间，不合并单调栈而是每个区间都询问一遍最小值，最多只有 $logn$ 个区间，在上面二分查找最小值并合并。单次询问是 $logn^2$ 的
然后我们考虑怎么插入一条直线
找到线段树上包含它的每一个区间，显然他一定是最后一个插入的直线，暴力插入
记录他顶掉了原单调栈的哪个元素以及原单调栈的大小，为还原做准备
由于他只会顶掉一个元素，显然是正确的
还原就把元素放回去…
空间问题的话，你可以开一个 $nlogn$ 的数组，给线段树每个区间分配长度
空间 $nlogn$ ，时间 $nlogn^2$
~~不过我跑的好慢啊~~

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define eps 1e-6
#define lc now<<1
#define rc now<<1|1
using namespace std;
const LL inf=(1LL<<63-1);
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(LL x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline void pr1(int x){write(x);printf(" ");}
inline void pr2(LL x){write(x);puts("");}
struct node{int x,y,next;LL c;}a[410000];int len,last[210000];
void ins(int x,int y,LL c){len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
struct line
{
	LL k,b,x;
	line(){}
	line(LL _k,LL _b,LL _x){k=_k;b=_b;x=_x;}
}w[20*410000],lst1[20*410000];int lst2[20*410000];
double getpt(line u1,line u2){return ((double)u2.b-u1.b)/((double)u1.k-u2.k);}
bool check(line u1,line u2,line u3)
{
	double s1=getpt(u1,u2),s2=getpt(u1,u3);
	return s1+eps>=s2;
}
int st[210000*4],ed[210000*4],tp[210000*4];

int ppp;
void buildtree(int now,int l,int r)
{
	st[now]=ppp;ed[now]=ppp+(r-l+1)-1;
	ppp+=(r-l+1);
	if(l==r)return ;
	int mid=(l+r)/2;
	buildtree(lc,l,mid);buildtree(rc,mid+1,r);
}
void push(int now,line u1)
{
	int temp=tp[now];
	while(temp>1&&check(w[st[now]+temp-2],w[st[now]+temp-1],u1))temp--;
	lst1[st[now]+u1.x-1]=w[st[now]+temp];lst2[st[now]+u1.x-1]=tp[now];
	w[st[now]+temp]=u1;tp[now]=temp+1;
}
void pop(int now,int p)
{
	if(w[st[now]+tp[now]-1].x!=p)return ;
	w[st[now]+tp[now]-1]=lst1[st[now]+p-1];tp[now]=lst2[st[now]+p-1];
}
void modify1(int now,int l,int r,int p,line u1)
{
	push(now,u1);
	if(l==r)return ;
	int mid=(l+r)/2;
	if(p<=mid)modify1(lc,l,mid,p,u1);
	else modify1(rc,mid+1,r,p,u1);
}
void modify2(int now,int l,int r,int p)
{
	pop(now,p);
	if(l==r)return ;
	int mid=(l+r)/2;
	if(p<=mid)modify2(lc,l,mid,p);
	else modify2(rc,mid+1,r,p);
}
LL calc(line p,LL x){return p.k*x+p.b;}
LL findans(int now,LL u1)
{
	int l=st[now],r=st[now]+tp[now]-1,ret;
	if(l>r)return inf;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(mid==st[now]+tp[now]-1)ret=mid,r=mid-1;
		else if(calc(w[mid],u1)<=calc(w[mid+1],u1))ret=mid,r=mid-1;
		else l=mid+1;
	}
	return calc(w[ret],u1);
}
LL query(int now,int l,int r,int ql,int qr,LL u1)
{
	if(l==ql&&r==qr)return findans(now,u1);
	int mid=(l+r)/2;
	if(qr<=mid)return query(lc,l,mid,ql,qr,u1);
	else if(mid+1<=ql)return query(rc,mid+1,r,ql,qr,u1);
	else
	{
		LL t1=query(lc,l,mid,ql,mid,u1);
		LL t2=query(rc,mid+1,r,mid+1,qr,u1);
		return min(t1,t2);
	}
}
LL ans[210000];
LL top,sum[210000];
LL ll[210000],p[210000],d[210000];
int n,m;
void dfs(int x,int fa,LL dep)
{
	if(x!=1)
	{
		int l=1,r=top,pos;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(dep-sum[mid]<=ll[x])pos=mid,r=mid-1;
			else l=mid+1;
		}
		ans[x]=query(1,1,n,pos,top,p[x]);
		ans[x]+=dep*p[x]+d[x];
	}
	sum[++top]=dep;
	modify1(1,1,n,top,line(-dep,ans[x],top));
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)dfs(y,x,dep+a[k].c);
	}
	modify2(1,1,n,top);top--;
}
int main()
{
	n=read();m=read();
	for(int i=2;i<=n;i++)
	{
		int fa=read();LL c=read();
		p[i]=read();d[i]=read();ll[i]=read();
		ins(fa,i,c);
	}
	ppp=1;buildtree(1,1,n);
	dfs(1,0,0);
	for(int i=2;i<=n;i++)pr2(ans[i]);
	return 0;
}

[bzoj3672][线段树][可持久化凸壳]购票

相关推荐