用CDQ分治维护凸壳

为什么会想到写这么一篇文章呢。。。
我怎么知道为什么!!

先从昨天模拟赛的题目开始吧
为什么现在的模拟赛里竟然会有ACM World Final的原题，这题以前在讲CDQ分治的时候在课件上看到过。。
然后我当时没有好好看。。(:з」∠)。。
导致我看到题面的时候的反应就是：
哇原题!
哇槽被我弃了的原题(:з」∠)

于是考场上的我只能自己YY了…

##Machine Works
你是任意性复杂机器公司(Arbitrarily Complex Machines, ACM)的经理,公司使用更加先进的机械设备生产先进的机器。原来的那一台生产机器已经坏了,所以你要去为公司买一台新的生产机器。你的任务是在转型期内尽可能得到更大的收益。在这段时间内,你要买卖机器,并且当机器被 ACM公司拥有的时候,操控这些机器以获取利润。因为空间的限制,ACM 公司在任何时候都只能最多拥有一台机器。在转型期内,有若干台可能卖出的机器。作为先进机器的专家,对于每台机器 M i ,你已经知道了其价格 P i 和可以买入的日期 D i 。注意,如果不在第 D i 天买入机器 M i ,那么别的人也会买走这一台机器,也就是说,以后你将没有机会购买这台机器了。如果 ACM 的钱低于一台机器的价格,那么你显然不可能买到这一台机器。如果你在第 D i 天买入了机器 M i ,那么 ACM 公司可以从第 D i + 1 天开始使用这一台机器。每使用这台机器一天,就可以为公司创造出 G i 美元的收益。你可以决定要在买入之后的某一天,以一定的折扣价卖出这一台机器。收购市场对于每一台机器,都有一个折扣价 R i。你不能在卖出的那一天使用机器,但是你可以在卖出的那一天再买入一台新的。在转型期结束后,ACM 公司会卖掉当前所拥有的机器。你的任务就是最大化转型期间ACM 公司可以得到的收入。
【输入格式】
输入包含若干组测试用例。每一组测试用例的第一行有 3 个正整数 N,C 和 D。N 是将会卖出的机器的台数(N ≤ 10 5 ),C 是在转型期开始时公司拥有的美元数量(C ≤ 10 9 ),D 是转型期持续的天数(D ≤ 10 9 )。之后的 N 行每一行描述了一台机器的情况。每一行有 4 个正整数 D i , P i , R i 和 G i ,分别表示这台机器卖出的时间,购买这台机器需要的美元数量,卖出这台机器的折扣价和使用这
台机器可以得到的利润。这些数字满足 1 ≤ D i ≤ D,1 ≤ R i < P i ≤ 10 9 且 1 ≤ G i ≤ 10 9 。最后一组测试用例后面的一行由 3 个 0 组成,表示输入数据结束。
【输出格式】
对于每一组测试用例,输出测试用例的编号,之后给出 ACM 公司在第 D + 1 天结束后可以得到的最大数量的美元。请依照下面给出的样例输出。

看到这道题目,很容易的想到了一个O(N^2)的DP,现将所有的机器按照买入时间排序,f[i]表示到第d[i]天时最大的收益,然后可以得到一个显然的方程$$f[i] = max (f[i-1],f[j]-p[j]+r[j]+(d[i]-d[j]-1)*g[j])(f[j]\geq p[j])$$看着这个东西好想可以斜率优化的样子..然后我就开始乱搞这个方程,对与从j和k两个位置的转移,j比k优的条件是$$f[j]-p[j]+r[j]+(d[i]-d[j]-1)*g[j]>=f[k]-p[k]+r[k]+(d[i]-d[k]-1)*g[k]$$这个式子太长了,我们发现其中的一部分只和jk自己有关,设$A[j] = f[j]-p[j]+r[j]-d[j]*g[j]-d[j]$,然后原式就可以化简为$$A[j]+d[i]*g[j]>=A[k]+d[i]*g[k]$$移项后得到$$d[i]<\frac{A[j]-A[k]}{g[j]-g[k]}$$推出来以后感觉很高兴啊,好像直接按照d排序以后斜率优化就好了..
然后开始码,码完以后一测样例过了好开心..
然后和暴力开始拍…几乎就是秒出错..(:з」∠)
调了一下数据以后发现…我忽略了g是不单调的..所以除过去以后符号可能会变..然后整个人就哔了狗了…

然后开始想怎么把这个正确性搞对呢…
突然发现!!!
这不就是用CDQ吗..
将原序列按时间分成两半,然后考虑前半段对后半段的影响的时候,可以把前半段按照g单调排序,然后就按照斜率优化的方法O(N)扫一遍,总的复杂度是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

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define ll long long
const ll N = 100100;
using namespace std;
ll read(){
	ll x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
struct data{ll d,p,r,g;} a[N];
struct node{ll g,A;} q[N],x[N];
ll n,c,d,f[N],sum,t,h,Cas,m;
bool cmp(const data &a,const data &b){return a.d<b.d;}
bool cmp1(const node &a,const node &b){if (a.g==b.g) return a.A<b.A;return a.g<b.g;}
double Slp(node j,node k) {return (double)(j.A-k.A)/(k.g-j.g);}
node operator - (const node &a,const node &b) { return (node){a.g-b.g,a.A-b.A};}
double Cross(const node &a,const node &b) { return 1.0*a.g*b.A-1.0*a.A*b.g;}
ll work(int i ,node p) {return p.A+p.g*a[i].d;}
void solve(ll l ,ll r){
	if(l==r){f[l] = max(f[l-1] , f[l]);return ;}
	int mid = (l+r)/2;
	solve(l, mid);
	sum = t = 0;h = 1;
	for(int i=l;i<=mid;i++) if(f[i]>=a[i].p) q[++sum] = (node){a[i].g,f[i]-a[i].p+a[i].r-(a[i].d+1)*a[i].g};
	sort(q+1,q+1+sum,cmp1);
	for(int i=1;i<=sum;i++){
		while(t>1 && Cross(x[t]-x[t-1],q[i]-x[t])>=0) t--;
		x[++t] = q[i];
	}
	for(int i=mid+1;i<=r;i++){
		while(h<t && work(i,x[h+1])>=work(i,x[h])) h++;
		if (h<=t) f[i] = max(f[i],work(i,x[h]));
	}
	solve(mid+1,r);
}
int main() {
	freopen("works.in","r",stdin);
	freopen("works.out","w",stdout);
	while (~scanf("%d%d%d",&n,&c,&d)) {
		if (n+c+d==0) return 0;Cas++;
		for (int i=1;i<=n;i++) a[i].d = read(),a[i].p = read(),a[i].r = read(),a[i].g = read();
		for (int i=1;i<=n+1;i++) f[i] = 0;
		f[0] = c;a[++n].d = d+1;
		sort(a+1,a+1+n,cmp);
		solve(1,n);
		printf("Case %d: %lld\n",Cas,f[n]);
	}
}

打完以后就开始了漫长的调试之路…
让我来想一下当时发生了什么:

sort的时候莫名其妙的RE了..后来发现是一个计算函数的锅…只要这个函数被调用..然后下一次排序就会RE..然而这是什么鬼一样的姿势啊..(:з」∠)..,到现在还是不知道到底为什么..
在更新后一半答案的时候非常霸气地把mid+1打成了1…(:з」∠)..哇槽什么鬼
中间TM还炸了longlong..(:з」∠)…

感觉很高兴啊,然后发现…华丽丽地卡了常数..(:з」∠)..(不过BZOJ上是很很轻松就过了的)
想想拿几分也就够了…然后没有去管他…
然而…最后FST了…被系统杀了…自信用%d读longlong..(:з」∠)…我是不是第一个用Ubuntu然后被Ubuntu系统杀的..(:з」∠)

直到讲课前我还一直以为CDQ是标算..毕竟如果直接用平衡树动态维护凸壳的常数和CDQ也差不了多少…

然后讲课的时候说,直接斜率优化然后在栈里面二分就好了…
诶什么情况..为什么可以斜率优化…

然后我又想了一下题面…发现最优策略里面g一定是递增的…(:з」∠)
哇槽这么显然的性质我竟然现在才发现.(:з」∠)..
然后根据这个性质可以直接按照g排序..然后维护一个斜率的单调栈,每次在栈里面二分,然后..这样也是log的..但是这个常数..(:з」∠)不说了..(:з」∠)
果真智商被虐的好惨

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

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
const ll N = 100010;
using namespace std;
struct data{ll d,p,r,g;} a[N];
ll split[N],n,c,d,f[N],ans,top,Cas;
pair <ll,ll> stk[N];
ll read(){
	ll x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
ll get(ll x) {
	if (!top) return -1ll<<60;
	ll l = 1,r = top-1,res = 0;
	if (x<=split[l]) return stk[l].first*x+stk[l].second;
	if (x>=split[r]) return stk[r+1].first*x+stk[r+1].second;
	while (l+1<r){
		ll mid = (l+r)>>1;
		if (split[mid]<x) l = mid;
		else r = mid;
	}
	return stk[r].first*x+stk[r].second;
}
bool cmp(data a,data b){return a.g<b.g;}
double Cross(double k1,double b1,double k2,double b2) {return (b2-b1)/(k1-k2);}
void Add(ll k,ll b){
	if (top && k==stk[top].first) {
		if (b<=stk[top].second) return;
		top--;
	}
	while (top>1 && Cross(stk[top-1].first,stk[top-1].second,k,b)<split[top-1]) top--;
	if (top) split[top] = Cross(stk[top].first,stk[top].second,k,b);
	stk[++top] = make_pair(k,b);
}
int main(){
	freopen("works.in","r",stdin);
	freopen("works.out","w",stdout);
	for (;;) {
		n = read();c = read();d = read();
		if (n+c+d==0) return 0;
		for (ll i=1;i<=n;i++) a[i].d = read(),a[i].p = read(),a[i].r = read(),a[i].g = read();
		ll ans = c;
		sort(a+1,a+1+n,cmp);top = 0;
		for (ll i=1;i<=n;i++) {
			f[i] = max(get(a[i].d),c)-a[i].p;
			if (f[i]>=0) {
				Add(a[i].g,f[i]+a[i].r-(a[i].d+1)*a[i].g);
				ans = max(ans,f[i]+(d-a[i].d)*a[i].g+a[i].r);
			}
		}
		printf("Case %lld: %lld\n",++Cas,ans);
	}
}

下午的时候去做了一下货币交换..感觉差不多的题目就写在一起了..

1492: [NOI2007]货币兑换Cash

点击这里去虐题

这道题是和上面一题一起出现在课件里的…
我们先考虑N^2的DP..讲道理这个dp好想并不是很好想….
显然的我们可以得到一个性质,每一次兑换货币的时候一定是全部兑换的,不会出现题面中的一部分的情况,所以我们只要知道了其中一种金券的数量就可以计算出另一种金券的数量.设f[i]表示第i天可以获得的最大价值,然后可以得到一个DP方程$$f[i] = max(f[i-1],\frac {f[j]*rate[j]*a[i]+f[j]*b[i]}{rate[j]*a[j]+b[j]})$$,其中$\frac{f[j]*rate[j]}{rate[j]*a[j]+b[j]}$表示第j天最多可以有多少A金券,我们设他为X[j],同样的$Y[j]=\frac{f[j]*rate[j]}{rate[j]*a[j]+b[j]}$,然后我们对上面的方程进行化简.对于两种转移j比k优的条件是$$f[j]*rate[j]*a[i]+f[j]*b[i]>f[k]*rate[k]*a[i]+f[k]*b[i]$$移项后得到$$\frac{f[j]-f[k]}{rate[j]*f[j]-rate[k]*f[k]}>-\frac{a[i]}{b[i]}$$然后就和上一题类似,按照$-\frac{a[i]}{b[i]}$排序,然后用CDQ分治维护凸壳..
不过这道题和上一道题有一点区别是,因为是根据$-\frac{a[i]}{b[i]}$排序的所以时间关系是乱的,分治的时候还是要按照时间分治,然后分别保证两端里要单调

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

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define N 120000
#define eps 1e-9
#define inf 1e9
using namespace std;
struct query{double q,a,b,rate,k;int pos;}q[N],nq[N];
double fabs(double x){return (x>0)?x:-x;}
struct point{
	double x,y;
	friend bool operator <(const point &a,const point &b) {	
		return (a.x<b.x+eps)||(fabs(a.x-b.x)<=eps&&a.y<b.y+eps);
	}
}p[N],np[N];
int st[N]; double f[N]; int n,m;
double getk(int i,int j){
	if (i==0) return -inf;
	if (j==0) return inf;
	if (fabs(p[i].x-p[j].x)<=eps) return -inf;
	return (p[i].y-p[j].y)/(p[i].x-p[j].x);
}
void solve(int l,int r){
	if (l==r){
		f[l]=max(f[l-1],f[l]);
		p[l].y=f[l]/(q[l].a*q[l].rate+q[l].b);
		p[l].x=p[l].y*q[l].rate;
		return ;
	}
	int mid=(l+r)>>1,l1=l,l2=mid+1;
	for (int i=l;i<=r;i++)
		if (q[i].pos<=mid) nq[l1++]=q[i];
		else nq[l2++]=q[i];
	for (int i=l;i<=r;i++) q[i]=nq[i];
	solve(l,mid);
	int top=0,j = 1;
	for (int i=l;i<=mid;i++){
		while (top>=2&&getk(i,st[top])+eps>getk(st[top],st[top-1])) top--;
		st[++top]=i;
	}
	for (int i=r;i>=mid+1;i--){
		while (j<top&&q[i].k<getk(st[j],st[j+1])+eps) j++;
		f[q[i].pos]=max(f[q[i].pos],p[st[j]].x*q[i].a+p[st[j]].y*q[i].b);
	}
	solve(mid+1,r);
	l1=l,l2=mid+1;
	for (int i=l;i<=r;i++)
		if ((p[l1]<p[l2]||l2>r)&&l1<=mid) np[i]=p[l1++];
		else np[i]=p[l2++];
	for (int i=l;i<=r;i++) p[i]=np[i];
}
bool cmp(query a,query b){return a.k<b.k;}
int main(){
	scanf("%d%lf",&n,&f[0]);
	for (int i=1;i<=n;i++) {
		scanf("%lf%lf%lf",&q[i].a,&q[i].b,&q[i].rate);
		q[i].k=-q[i].a/q[i].b;
		q[i].pos=i;
	}
	sort(q+1,q+n+1,cmp);
	solve(1,n);
	printf("%.3lf\n",f[n]);
}

有错误请指出$$\mathcal {FIN}$$