「NOI2014」购票 解题报告

时间：2022-11-04 16:04:44

「NOI2014」购票

写完了后发现写的做法是假的...然后居然过了，然后就懒得管正解了。

发现需要维护凸包，动态加点，询问区间，强制在线

可以二进制分组搞，然后你发现在树上需要资瓷撤回，然后暴力撤回（雾

然后就被卡了

卡法，在\(2^k-1\)位置搞一朵菊花

先留坑，以后要是会了一些神奇的姿势就来搞

这题叉积会爆ll，坑

Code:

#include <cstdio>

#include <cctype>

#include <vector>

#include <algorithm>

#define ll long long

const int N=2e5+10;

using std::min;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int head[N],to[N],Next[N],cnt;ll edge[N];

int n,t;

void add(int u,int v,ll w)

{

	to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;

}

struct Point

{

	ll x,y;

	Point(){}

	Point(ll X,ll Y){x=X,y=Y;}

	Point friend operator -(Point a,Point b){return Point(a.x-b.x,a.y-b.y);}

	bool friend operator <(Point a,Point b){return a.x==b.x?a.y<b.y:a.x<b.x;}

};

long double Cross(Point a,Point b){return 1.0*a.x*b.y-1.0*a.y*b.x;}

std::vector<Point> s[N<<2],pot[N<<2],yuu;

void ins(int id,Point x)

{

	int tot=s[id].size()-1;

	while(tot>0&&Cross(s[id][tot]-s[id][tot-1],x-s[id][tot])<=0) --tot,s[id].pop_back();

    s[id].push_back(x);

}

void build(int id)

{

	yuu=pot[id];

	std::sort(yuu.begin(),yuu.end());

	s[id].clear();

	for(int i=0;i<yuu.size();i++) ins(id,yuu[i]);

}

#define ls id<<1

#define rs id<<1|1

void add(int id,int l,int r,int p,Point ins)

{

	pot[id].push_back(ins);

	if(pot[id].size()==r+1-l) build(id);

	if(l==r) return;

	int mid=l+r>>1;

	if(p<=mid) add(ls,l,mid,p,ins);

	else add(rs,mid+1,r,p,ins);

}

void del(int id,int l,int r,int p)

{

	pot[id].pop_back();

	if(l==r) return;

	int mid=l+r>>1;

	if(p<=mid) del(ls,l,mid,p);

	else del(rs,mid+1,r,p);

}

ll cal(Point a,ll k){return a.y-k*a.x;}

ll yuucute(int id,ll k)

{

	int l=0,r=s[id].size()-1;

	while(l<r)

	{

		int mid=l+r>>1;

		if(cal(s[id][mid],k)>cal(s[id][mid+1],k)) l=mid+1;

		else r=mid;

	}

	return cal(s[id][l],k);

}

ll query(int id,int L,int R,int l,int r,ll k)

{

	if(l==L&&r==R) return yuucute(id,k);

	int Mid=L+R>>1;

	if(r<=Mid) return query(ls,L,Mid,l,r,k);

	else if(l>Mid) return query(rs,Mid+1,R,l,r,k);

	else return min(query(ls,L,Mid,l,Mid,k),query(rs,Mid+1,R,Mid+1,r,k));

}

int f[N][20],dep[N];ll fd[N][20];

int Find(int x,ll d)

{

	for(int i=18;~i;i--)

		if(fd[x][i]<=d)

			d-=fd[x][i],x=f[x][i];

	return dep[x];

}

ll ans[N],p[N],q[N],l[N];

void dfs(int now,ll d,int rp)

{

    dep[now]=rp;

	for(int i=1;i<=18;i++) f[now][i]=f[f[now][i-1]][i-1],fd[now][i]=fd[now][i-1]+fd[f[now][i-1]][i-1];

	int lp=l[now]>=d?1:Find(now,l[now]);

	ans[now]=query(1,1,n,lp,rp-1,p[now])+q[now]+d*p[now];

	add(1,1,n,rp,Point(d,ans[now]));

	for(int i=head[now];i;i=Next[i])

		dfs(to[i],d+edge[i],rp+1);

	del(1,1,n,rp);

}

int main()

{

	read(n),read(t);

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

	{

		read(f[i][0]),read(fd[i][0]);

		add(f[i][0],i,fd[i][0]);

		read(p[i]),read(q[i]),read(l[i]);

	}

	add(1,1,n,1,Point(0,0));dep[1]=1;

	for(int i=head[1];i;i=Next[i])

		dfs(to[i],edge[i],2);

	for(int i=2;i<=n;i++) printf("%lld\n",ans[i]);

	return 0;

}

2019.2.22

相关文章