怎么网上题解都是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]);
}

第一次打BST，不会打便去网上搜模板，可是都写得好复杂，让刚入门C++的我很多看不懂。百度百科了一下，了解了思路，自己yy出了代码，原来很短啊。

#include<cstdio>
#include<cstring>
using namespace std;
int n,i,tot,x;
struct node{
    int l,r,v;
}a[100005];
bool first;
void ins(int t)
{
    if (a[t].v==0) {a[t].v=x;return;}
    if (x<=a[t].v)
    {
        if (a[t].l==0) {tot++; a[t].l=tot;}
        ins(a[t].l);
    }
    else
    {
        if (a[t].r==0) {tot++; a[t].r=tot;}
        ins(a[t].r);
    }
}
void print(int t)
{
    if (first) first=0,printf("%d",a[t].v);else printf(" %d",a[t].v);
    if (a[t].l) print(a[t].l);
    if (a[t].r) print(a[t].r);
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        tot=1;
        for (i=1;i<=n;i++)
        {
            scanf("%d",&x);
            ins(1);
        }
        first=1;
        print(1);
        printf("\n");
    }
}