题目链接：

http://uoj.ac/problem/7

思路：

如果没有距离限制L的话只要dfs一遍同时维护到根的凸壳就可以（二分位置后可以做到O（1）添加，O（1）恢复）。

这题有个距离限制的话就可以将重心下面的点按d[v]-l[v]排序后，与重心到根的点一起双指针更新。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200005;
struct E
{
	int v; ll z;
};
vector<E>link[N];
ll d[N],p[N],q[N],l[N],f[N];
int fa[N];

struct P
{
	ll d,f;
	ll operator*(const P &b)const
	{
		return d*b.d+f*b.f;
	}
}stk[N];
int top;
long double slope(P a,P b)
{
    long double tmp=1.0;
    return tmp*(b.f-a.f)/(b.d-a.d);
}
void add(P p)
{
	if (top<=1)
	{
		stk[top++]=p;
		return;
	}
	while(top>=2&&slope(p,stk[top-1])>slope(stk[top-1],stk[top-2])) top--;
	stk[top++]=p;
}
void upd(int id)
{
	P vec={-p[id],1};
	int l=0,r=top-1;
	while(l<r)
	{
		int mid=(l+r)/2;
		if (vec*stk[mid]>vec*stk[mid+1]) l=mid+1;
		else r=mid;
	}
	f[id]=min(f[id],p[id]*d[id]+q[id]+vec*stk[l]);
}

int cent,mxsz;
int size[N];
int vis[N];
void findcent(int u,int n)
{
	size[u]=1;
	int mx=0;
	for (E e:link[u])
	{
		int v=e.v;
		if (vis[v]) continue;
		d[v]=d[u]+e.z;
		findcent(v,n);
		size[u]+=size[v];
		mx=max(mx,size[v]);
	}
	mx=max(mx,n-size[u]);
	if (mx<=mxsz) cent=u,mxsz=mx;
}

int nd[N],tot;
void add(int u)
{
	nd[tot++]=u;
	for (E e:link[u])
		if (!vis[e.v]) add(e.v);
}
bool cmp(int i,int j)
{
	return d[i]-l[i]>d[j]-l[j];
}
void solve(int u,int n)
{
	if (n==1) return;
	cent=u;  mxsz=n;
	findcent(u,n);
	int rt=cent;
	for (E e:link[rt]) vis[e.v]++;
	if (u==4&&n==2)
		u=4;
	solve(u,n-size[rt]+1);

	for (E e:link[rt]) vis[e.v]--;
	for (E e:link[rt]) add(e.v);
	sort(nd,nd+tot,cmp);
	int now=rt;
	for (int i=0;i<tot;i++)
	{
		int id=nd[i];
		while(now!=fa[u]&&d[now]>=d[id]-l[id]) add({d[now],f[now]}),now=fa[now];
		if (top) upd(id);
	}
	tot=0; top=0;
	for (E e:link[rt]) solve(e.v,size[e.v]);
}
int main()
{
	int n,t; scanf("%d%d",&n,&t);
	for (int i=2;i<=n;i++)
	{
		f[i]=1ll<<62;
		ll s; scanf("%d%lld",&fa[i],&s);
		link[fa[i]].push_back({i,s});
		scanf("%lld%lld%lld",&p[i],&q[i],&l[i]);
	}
	solve(1,n);
	for (int i=2;i<=n;i++) printf("%lld\n",f[i]);
}

题意：

一棵树，1为根。每个点只能走向祖先，时间为距离的平方，另外走到祖先后会停留P单位时间。求每个点到达根的最小时间的最大值。

思路：

显然dp方程为:f[i]=(d[i]-d[j])^2+P+f[j]  ( j 是 i 的祖先）

转化成向量点积形式：f[i]=d[i]^2+P+(1 , 2*d[i] ) * ( f[j]+d[j]^2 , -d[j] )

注意到深度越大，向量(1 , 2*d[i] )会逆时针旋转

于是维护点集i的所有祖先的  ( f[j]+d[j]^2 , -d[j] ) 的下凸壳，就能求出f[i]的最小值

注意到向量( f[j]+d[j]^2 , -d[j] )只会添加在下凸壳右边，于是只要用个队列来保存就可以了

查询的时候只要一直扔掉左边的点，找到最大值为止，然后退出当前dfs的时候加回来就可以了

如果一个个保存删掉的点，再一个个加回来的话，在菊花图的情况下复杂度就会变成O（n^2），事实上目前网上的题解都是这么做的，估计出题人也没意识到复杂度的问题，因为这看起来很像O（n）。

我的做法是每次dfs记录当前队列的左端点，和右端点，操作完后，事实上只是替换了数组里的tail位置的元素，把head和tail还有这个元素事先保存下来，最后恢复head，tail和这个元素就可以了，这样复杂度就是完美的O（n）了。

也不知道这种做法叫什么，毕竟自己乱想出来的，就叫回溯队列好了233

后来一想这个做法还是n方。。。因为每次head和tail的删除操作都可能是O（n）的，所以要二分查找head和tail分别应该删到哪，这样算法复杂度就是O（nlogn）了

这里如果不用斜率，而把两边的dx都乘到对面去的话是有问题的，因为f[j]+d[j]^2的规模是1e14，2*d[i]的规模是1e7，乘起来理论上会爆，然而数据好像还是没卡掉这种做法

代码1：O（n^2）做法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
struct P
{
	ll x,y;
	ll operator*(const P &b)const
	{
		return x*b.x+y*b.y;
	}
}stk[N];
int n,p;
int head,tail;
vector<P>link[N];
ll f[N],d[N];
long double slope(P a,P b)
{
	long double tmp=1.0;
	return tmp*(b.y-a.y)/(b.x-a.x);
}
void dfs(int u,int fa,int deep)
{
	int phead=head,ptail=tail;
	d[u]=deep;
	if (u==1) f[u]=-p;
	else
	{
		P tmp={1,2*d[u]};
		while(tail-head+1>=2&&stk[head]*tmp>=stk[head+1]*tmp) head++;
		f[u]=d[u]*d[u]+p+stk[head]*tmp;
	}
	P tmp={f[u]+d[u]*d[u],-d[u]};
	while(tail-head+1>=2&&
		slope(stk[tail-1],stk[tail])>=slope(stk[tail],tmp)) tail--;
	P mem=stk[tail+1];
	stk[++tail]=tmp;

	for (int i=0;i<link[u].size();i++)
	{
		int v=link[u][i].x;
		if (v==fa) continue;
		dfs(v,u,deep+link[u][i].y);
	}
	tail--;
	stk[tail+1]=mem;
	head=phead; tail=ptail;
}
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&p);
		for (int i=1;i<n;i++)
		{
			ll x,y,z;
			scanf("%d%d%lld",&x,&y,&z);
			if (z<0) n/=0;
			link[x].push_back({y,z});
		}
		head=1; tail=0;
		dfs(1,1,0);
		ll ans=0;
		for (int i=1;i<=n;i++) ans=max(ans,f[i]);
		printf("%lld\n",ans);

		for (int i=1;i<=n;i++) link[i].clear();
	}
}

代码2：O（nlogn）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
struct P
{
    ll x,y;
    ll operator*(const P &b)const
    {
        return x*b.x+y*b.y;
    }
}stk[N];
int n,p;
int head,tail;
vector<P>link[N];
ll f[N],d[N];
long double slope(P a,P b)
{
    long double tmp=1.0;
    return tmp*(b.y-a.y)/(b.x-a.x);
}
int gethead(P v)
{
	int l=head,r=tail;
	while(l<r)
	{
		int mid=(l+r)/2;
		if (stk[mid]*v>=stk[mid+1]*v) l=mid+1;
		else r=mid;
	}
	return l;
}
int gettail(P v)
{
	int l=head,r=tail;
	while(l<r)
	{
		int mid=(l+r)/2;
		if (slope(stk[mid],stk[mid+1])<slope(stk[mid+1],v)) l=mid+1;
		else r=mid;
	}
	return l;
}
void dfs(int u,int fa,int deep)
{
    int phead=head,ptail=tail;
    d[u]=deep;
    if (u==1) f[u]=-p;
    else
    {
        P tmp={1,2*d[u]};
        head=gethead(tmp);

        //while(tail-head+1>=2&&stk[head]*tmp>=stk[head+1]*tmp) head++;
        f[u]=d[u]*d[u]+p+stk[head]*tmp;
    }
    P tmp={f[u]+d[u]*d[u],-d[u]};
    tail=gettail(tmp);
//    while(tail-head+1>=2&&
//        slope(stk[tail-1],stk[tail])>=slope(stk[tail],tmp)) tail--;
    P mem=stk[tail+1];
    stk[++tail]=tmp;

    for (int i=0;i<link[u].size();i++)
    {
        int v=link[u][i].x;
        if (v==fa) continue;
        dfs(v,u,deep+link[u][i].y);
    }
    tail--;
    stk[tail+1]=mem;
    head=phead; tail=ptail;
}
int main()
{
    int t; scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&p);
        for (int i=1;i<n;i++)
        {
            ll x,y,z;
            scanf("%d%d%lld",&x,&y,&z);
            link[x].push_back({y,z});
        }
        head=1; tail=0;
        dfs(1,1,0);
        ll ans=0;
        for (int i=1;i<=n;i++) ans=max(ans,f[i]);
        printf("%lld\n",ans);

        for (int i=1;i<=n;i++) link[i].clear();
    }
}

怎么网上题解都是cdq分治做的啊。。。

题意什么的最近都懒得写了。。看这里http://blog.csdn.net/sdj222555/article/details/40919903

n方暴力很好想，f[i]= f[j] + (d[i]-d[j]-1) * G[j] + R[j] - P[i] 。

写成向量点积形式 f[i]= ( d[i] , 1 ) * ( G[j] , f[j]+R[j]-(d[j]+1])*G[j] )  - p[i] 。

把所有的 j 都 扔到平衡树里维护个上凸壳 就好了。

注意到 d[i] 是递增的，于是也不需要二分查找了。

貌似还是cdq写起来简单点？不过平衡树好想啊。

#include<cstdio>
#include<map>
#include<algorithm>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef map<ll,ll>::iterator itr;
struct P
{
	ll x,y;
	P operator-(const P &t)const
	{
		return {x-t.x,y-t.y};
	}
	ll operator^(P t)
	{
		return x*t.y-y*t.x;
	}
};
ll dot(itr it,ll x,ll y)
{
	return it->X*x+it->Y*y;
}
ll cross(itr l,P p2,itr r)
{
	P p1={l->X,l->Y},p3={r->X,r->Y};
	return (p2-p1)^(p3-p2);
}
struct hull
{
	map<ll,ll>s;
	itr mid,l,r,p1,p2;
	void init() { s.clear(); }
	itr pre(itr it)
	{
		if (it==s.end()) return it;
		if (it==s.begin()) return s.end();
		return --it;
	}
	itr suc(itr it)
	{
		if (it==s.end()) return it;
		return ++it;
	}
	bool inside(P p)
	{
		if (s.empty()) return 0;
		r=s.lower_bound(p.x);
		if (r==s.end()) return 0;
		if (r->X==p.x) return p.y<=r->Y;
		if (r==s.begin()) return 0;
		l=r; l--;
		return cross(l,p,r)>=0;
	}
	void add(P p)
	{
		if (inside(p)) return;
		s[p.x]=p.y;
		mid=s.find(p.x);
		p1=suc(mid); p2=suc(p1);
		while(p1!=s.end()&&p2!=s.end()&&cross(mid,{p1->X,p1->Y},p2)>=0)
			s.erase(p1),p1=p2,p2=suc(p2);
		p1=pre(mid); p2=pre(p1);
		while(p1!=s.end()&&p2!=s.end()&&cross(mid,{p1->X,p1->Y},p2)<=0)
			s.erase(p1),p1=p2,p2=pre(p2);
	}
	ll get(ll x,ll y)
	{
		l=s.begin();
		r=suc(l);
		while(r!=s.end()&&dot(l,x,y)<=dot(r,x,y))
			s.erase(l),l=r,r=suc(r);
		return dot(l,x,y);
	}
}G;

const int N=100005;
int n,C,D;
struct mac
{
	int d,P,R,G;
}a[N];
bool cmp(mac a,mac b){ return a.d<b.d;}
ll f[N];

int main()
{
	int cas=0;
	while(scanf("%d%d%d",&n,&C,&D),n+C+D)
	{
		for (int i=1;i<=n;i++)
			scanf("%d%d%d%d",&a[i].d,&a[i].P,&a[i].R,&a[i].G);
		sort(a+1,a+n+1,cmp);
		a[0]={0,0,0,0};
		f[0]=C;
		n++;
		a[n]={D+1,0,0,0};
		G.init();
		G.add({a[0].G,f[0]});
		for (int i=1;i<=n;i++)
		{
			f[i]=G.get(a[i].d,1)-a[i].P;
			if (f[i]>=0) G.add({a[i].G,f[i]+a[i].R-1ll*(a[i].d+1)*a[i].G});
		}
		printf("Case %d: %lld\n",++cas,f[n]);
	}
}

题意： 

Bessie考了N科（N≤50000），每科的得分为Ti，满分为Pi（样例似乎是五科红灯……）。

现在Bessie的老师要给她们统计最终得分，方法 是先算出每一科得分的百分比，去除D个百分比最低的科目，然后剩下科目的∑T / ∑P就是最终得分的百分比。

很幸运，没有人有两科的得分比一样。Bessie的数学很牛X，她马上就发现她的老师在坑爹，因为有时候可以通过去除不同的科 目来获得更高的分数。

现在Bessie想知道，对于哪些D值，她可以通过去除与老师不同的D科，从而获得更高的分数呢？

（摘自http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html）

做法：

假设现在取了i个百分比靠前的科目，当前的综合百分比是k。

如果能把选的科目p替换成一个没选的科目q使得综合百分比提高 ，根据01分数规划的思想，显然 p.T-k*p.P<q.T-k*q.P 。

于是就可以在选的科目中找一个科目 p 使得 p.T-k*p.P最小，再在没选的科目中找一个科目 q 使 q.T-k*q.P 最大 。

然后发现 T-k*P 就是向量的点积 （1,-k)*(T,P) ，就可以用平衡树维护两个凸壳来找最大值和最小值。

注意到：排序后 选的科目越多，综合百分比越低，因此k是单调的，于是便不需要在平衡树里二分查找了。

网上题解说可以用单调栈，但是总感觉有问题，还是用了平衡树。

我依旧是把上凸壳转化成下凸壳用同一个函数来做。

#include<cstdio>
#include<map>
#include<algorithm>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef map<int,int>::iterator itr;
const int N=50005;
int n;
double k[N],fmax[N],fmin[N];
int ans[N];
struct P
{
	int x,y;
	P operator-(const P &t)const
	{
		return {x-t.x,y-t.y};
	}
	int operator^(P t)
	{
		return x*t.y-y*t.x;
	}
}a[N];
bool cmp(P a,P b)
{
	return 1.0*a.y/a.x>1.0*b.y/b.x;
}
double dot(itr it,double x,double y)
{
	return it->X*x+it->Y*y;
}
ll cross(itr l,P p2,itr r)
{
	P p1={l->X,l->Y},p3={r->X,r->Y};
	return (p2-p1)^(p3-p2);
}
struct hull
{
	map<int,int>s;
	itr mid,l,r,p1,p2;
	void init() { s.clear(); }
	itr pre(itr it)
	{
		if (it==s.end()) return it;
		if (it==s.begin()) return s.end();
		return --it;
	}
	itr suc(itr it)
	{
		if (it==s.end()) return it;
		return ++it;
	}
	bool inside(P p)
	{
		if (s.empty()) return 0;
		r=s.lower_bound(p.x);
		if (r==s.end()) return 0;
		if (r->X==p.x) return p.y>=r->Y;
		if (r==s.begin()) return 0;
		l=r; l--;
		return cross(l,p,r)<=0;
	}
	void add(P p)
	{
		if (inside(p)) return;
		s[p.x]=p.y;
		mid=s.find(p.x);
		p1=suc(mid); p2=suc(p1);
		while(p1!=s.end()&&p2!=s.end()&&cross(mid,{p1->X,p1->Y},p2)<=0)
			s.erase(p1),p1=p2,p2=suc(p2);
		p1=pre(mid); p2=pre(p1);
		while(p1!=s.end()&&p2!=s.end()&&cross(mid,{p1->X,p1->Y},p2)>=0)
			s.erase(p1),p1=p2,p2=pre(p2);
	}
	double get(double x,double y)
	{
		r=s.end(); r--;
		l=pre(r);
		while(l!=s.end()&&dot(l,x,y)<=dot(r,x,y))
			s.erase(r),r=l,l=pre(l);
		return dot(r,x,y);
	}
}G;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].y,&a[i].x);
	sort(a+1,a+n+1,cmp);
	double sumT=0,sumP=0;
	for (int i=1;i<=n;i++) sumT+=a[i].y,sumP+=a[i].x,k[i]=sumT/sumP;
	G.init();
	for (int i=1;i<=n;i++)
	{
		G.add(a[i]);
		fmin[i]=G.get(-k[i],1);
	}
	G.init();
	for (int i=n;i>=2;i--)
	{
		G.add({a[i].x,-a[i].y});
		fmax[i-1]=-G.get(k[i-1],1);
	}
	int cnt=0;
	for (int i=1;i<n;i++)
		if (fmin[i]<fmax[i]) ans[++cnt]=n-i;
	printf("%d\n",cnt);
	for (int i=cnt;i>=1;i--) printf("%d\n",ans[i]);
}

参考了这篇博客 http://blog.csdn.net/u013912596/article/details/47978791 

我的做法：

其实每次询问就是 找一个向量(x,y)使得 （x,y)*(p,q)最大。根据向量点积的性质很容易发现最优的向量肯定在凸包上。

如果没有删除操作，可以用平衡树来维护上凸壳和下凸壳，每次询问二分查找。

这题有删除操作，看了题解再想了很久才知道怎么分治。

对于一个操作区间【L,R】：

如果【L,mid】区间内的添加的向量在 R 之后被删除或者不删，那么就可以用它们构建上下凸壳来更新【mid+1,R】区间内的询问。

如果【mid+1，R】区间内的删除的向量在 L 之前添加，那么也可以用它们构建上下凸壳来更新【L,mid】区间内的询问。

然后就做完了。

一些小技巧：下凸壳可以翻转一下变成上凸壳用同样的方法维护，nxt数组记录与操作i相关的另一个操作的位置，可以很方便的判断它是添加操作还是删除操作。

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=50005;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n;
ll ans[N];
int nxt[N];
struct P
{
	int x,y;
	bool operator<(const P &t)const
	{
		return x<t.x||x==t.x&&y>t.y;
	}
	P operator-(const P &t)
	{
		return {x-t.x,y-t.y};
	}
	ll operator*(const P &t)
	{
		return 1ll*x*t.x+1ll*y*t.y;
	}
	ll operator^(const P &t)
	{
		return 1ll*x*t.y-1ll*y*t.x;
	}
}a[N];
ll cross(P a,P b,P c)
{
	return (b-a)^(c-b);
}
map<P,int>mp;
struct hull
{
	int n,top;
	P a[N],stk[N];
	void init()
	{
		n=0;
	}
	void add(P p)
	{
		a[++n]=p;
	}
	void make()
	{
		sort(a+1,a+n+1);
		top=0;
		for (int i=1;i<=n;i++)
		{
			while(top>1&&cross(stk[top-1],stk[top],a[i])>=0) top--;
			stk[++top]=a[i];
		}
	}
	ll get(P p)
	{
		if (top==0) return -INF;
		int l=1,r=top;
		while(l<r)
		{
			int mid=(l+r)/2;
			if (p*stk[mid]<p*stk[mid+1]) l=mid+1;else r=mid;
		}
		return p*stk[l];
	}
}up,down;
void solve(int l,int r)
{
	if (l==r) return;
	int mid=(l+r)/2;

	up.init(); down.init();
	for (int i=l;i<=mid;i++)
		if (nxt[i]>r)
		{
			up.add(a[i]);
			down.add({a[i].x,-a[i].y});
		}
	up.make(); down.make();
	for (int i=mid+1;i<=r;i++)
		if (nxt[i]==i)
		{
			ans[i]=max(ans[i],up.get(a[i])),
			ans[i]=max(ans[i],down.get({a[i].x,-a[i].y}));
		}

	up.init(); down.init();
	for (int i=mid+1;i<=r;i++)
		if (nxt[i]<l)
		{
			up.add(a[i]);
			down.add({a[i].x,-a[i].y});
		}
	up.make(); down.make();
	for (int i=l;i<=mid;i++)
		if (nxt[i]==i)
		{
			ans[i]=max(ans[i],up.get(a[i]));
			ans[i]=max(ans[i],down.get({a[i].x,-a[i].y}));
		}

	solve(l,mid);
	solve(mid+1,r);
}
int main()
{
	while(scanf("%d",&n),n)
	{
		mp.clear();
		for (int i=1;i<=n;i++) ans[i]=-INF;
		for (int i=1;i<=n;i++)
		{
			int tp;
			scanf("%d%d%d",&tp,&a[i].x,&a[i].y);
			if (tp==1) nxt[i]=n+1,mp[a[i]]=i;
			if (tp==-1)
			{
				int id=mp[a[i]];
				nxt[id]=i; nxt[i]=id;
				mp.erase(a[i]);
			}
			if (tp==0) nxt[i]=i;
		}
		solve(1,n);
		for (int i=1;i<=n;i++)
			if (nxt[i]==i) printf("%lld\n",ans[i]);
	}
}