题意：
略
见上一篇
题解：
方程还是那个方程f[i]=A[i] * X[j] + B[i] * Y[j]；
化简为Y[i]=(-A[i]/B[i]) * X[i] + f[i]/B[i]这一坨；
既然这个斜率不单调，那排个序让它单调不就行了；
排序之后的问题就是，在i前面更新i的点不一定可以更新i，而应该用来更新i的点说不定还在i的后面；
那么这时候就是用CDQ分治解决；
经典的四步先贴上来：
1.将操作按照时间划分为两个子区间；2.递归处理左区间的修改与询问；3.用左区间的修改处理右区间的询问；4.递归处理右区间的修改与询问；
光这么四句话肯定没用，下面是具体的；
动态规划中对f[i]的更新相当于是查询，而用f[i]来更新别人则相当于是一次修改；
那么在将所有的点按斜率排序之后，进行一个分治的solve(1,n)，然后按四步走；
1.划分区间：
这里的时间就是天数，只需要取一个mid然后用mid把点分成两堆；
注意这里划分了以后，两个区间仍按斜率有序，并且左区间的全部时间都小于右区间的全部时间；
2.递归处理左区间：
递归下去要有一个边界，这里的边界显然就是l==r的时候；
这时这个结点前面的结点都已经对它更新了；
所以它在更新一下f[i-1]就是最终的f[i]，顺便计算出X[i]Y[i]的值；
然后每层递归结束时要按X[i]排序(为了维护凸包方便)(这样的递归结构下用归并的线性显然比快拍要好)；
3.用左区间修改右区间：
左区间已经按X[i]排序完成，可以扫一遍求出凸包；
右区间现在还是按斜率排序，直接上斜率优化；
这时候右区间的所有点已经被左区间的点处理完了；
4.递归处理右区间：
被左区间处理了的点还要被右区间在它前面的点处理，，所以再递归搞一下；
然后就结束了，f[n]就是答案；
这些操作全都是线性复杂度的，而一共递归有logn层，复杂度为O(nlogn)；
排完序之后的下标不是时间。。。sort写错的去看眼科大夫。。。
代码2k+，时间1232ms；
居然没有平衡树跑得快，但是代码上的确是省了不少；
顺便一提，bz AC50题留念(笑)；
代码：
#include<math.h> #include<stdio.h> #include<string.h> #include<algorithm> #define N 110000 #define which(x) (tr[tr[x].fa].ch[1]==x) const double INF = 1e100; const double EPS = 1e-8; using namespace std; struct node {double x, y, slope;int no; }a[N], temp[N]; double f[N], A[N], B[N], R[N]; int st[N]; int cmp(node a, node b) {return a.slope < b.slope; } double slope(int x, int y) {if (fabs(a[x].x – a[y].x) < EPS)return a[x].y < a[y].y ? INF : -INF;elsereturn (a[x].y – a[y].y) / (a[x].x – a[y].x); } void merge(int l, int r) {memcpy(temp + l, a + l, sizeof(node)*(r – l + 1));int mid = (l + r) >> 1, i, j, k;for (k = l, i = l, j = mid + 1; k <= r; k++){if (i <= mid&&j <= r)a[k] = temp[i].x < temp[j].x ? temp[i++] : temp[j++];elsea[k] = (i == mid + 1 ? temp[j++] : temp[i++]);} } void slove(int l, int r) {if (l == r){f[l] = max(f[l], f[l – 1]);a[l].y = f[l] / (A[l] * R[l] + B[l]);a[l].x = R[l] * a[l].y;}else{int mid = (l + r) >> 1, i, j, k, top;for (i = l, j = l, k = mid + 1; i <= r; i++)if (a[i].no <= mid)temp[j++] = a[i];elsetemp[k++] = a[i];memcpy(a + l, temp + l, sizeof(node)*(r – l + 1));slove(l, mid);st[top = 1] = l;for (i = l + 1; i <= mid; i++){while (top >= 2 && slope(st[top – 1], st[top]) < slope(st[top], i))top–;st[++top] = i;}for (i = mid + 1; i <= r; i++){while (top >= 2 && slope(st[top – 1], st[top]) < a[i].slope)top–;f[a[i].no] = max(f[a[i].no], A[a[i].no] * a[st[top]].x + B[a[i].no] * a[st[top]].y);}slove(mid + 1, r);merge(l, r);} } int main() {int n, i, j, k;double ans;scanf("%d%lf", &n, &f[1]);for (i = 1; i <= n; i++)scanf("%lf%lf%lf", A + i, B + i, R + i),a[i].slope = -A[i] / B[i],a[i].no = i;sort(a + 1, a + n + 1, cmp);slove(1, n);printf("%.3lf", f[n]);return 0; }
上帝助自助者。
