[Uva 1106][DP][操作分治] Machine Works

原題連結
 這裡 是這題完整的想法以及支持在線的作法，特地再寫一篇是因為像操作分治一類轉離線後的作法不僅code量少，時間和空間上的表現也都很優秀。


平衡樹維護凸包我寫得要死要活寫了三天，操作分治40min就AC了，而且de最久的bug依然是__int128.....這數據實在是太坑了。

和整體二分的思想類似，只不過算法本身並沒有二分搜的性質，而是單純利用分治的特性讓複雜度從O(n^2)掉成O(nlogn)。

剩下的就參考code吧，概念和實作都算挺好懂的。

#define LL __int128
#include<bits/stdc++.h>
using namespace std;
const LL maxn=100000+5;
struct Machine
{
    LL day,price,resold,gene;
    bool operator < (const Machine& rhs) const {return day<rhs.day;}
}Mac[maxn];
struct Line
{
    LL slope,inter;
    Line(LL s,LL i):slope(s),inter(i) {}
    LL getVal(LL x){return slope*x+inter;}
    bool operator < (const Line& rhs) const {return slope<rhs.slope || (slope==rhs.slope && inter<rhs.inter);}
};
LL N,C,D;
vector<Line> line,hull;
LL dp[maxn];
bool check(Line& L0,Line& L1,Line& L2)
{
    return (L2.inter-L0.inter)*(L0.slope-L1.slope)< (L0.slope-L2.slope)*(L1.inter-L0.inter);
}
void update(LL tL,LL tR)
{
    LL tM=tL+(tR-tL)/2;
    line.clear();
    for(LL i=tL;i<=tM;i++) if(dp[i]>=Mac[i].price)
        line.push_back(Line(Mac[i].gene,Mac[i].resold-Mac[i].price+dp[i]-(Mac[i].day+1)*Mac[i].gene));
    sort(line.begin(),line.end());
    hull.clear();
    for(Line now:line)
    {
        while(hull.size() && hull[hull.size()-1].slope==now.slope) hull.pop_back();
        while(hull.size()>1 && check(hull[hull.size()-2],hull[hull.size()-1],now)) hull.pop_back();
        hull.push_back(now);
    }
    LL now=0;
    for(LL i=tM+1;i<=tR;i++)
    {
        LL day=Mac[i].day;
        while(now+1<hull.size() && hull[now].getVal(day)<hull[now+1].getVal(day)) now++;
        dp[i]=max(dp[i],hull[now].getVal(day));
    }
}
void CDQ(LL L,LL R)
{
    if(L==R) return;
    LL M=L+(R-L)/2;
    CDQ(L,M);
    update(L,R);
    CDQ(M+1,R);
}
int main()
{
//    freopen("in","r",stdin);
    long long kase=0,NN,CC,DD;
    while(scanf("%lld%lld%lld",&NN,&CC,&DD)==3 && NN && CC && DD)
    {
        N=NN,C=CC,D=DD;
        memset(dp,0,sizeof dp);
        for(long long i=1,a,b,c,d;i<=N;i++) {scanf("%lld%lld%lld%lld",&a,&b,&c,&d);Mac[i].day=a,Mac[i].price=b,Mac[i].resold=c,Mac[i].gene=d;}
        Mac[0]=Machine{0,0,C,0};
        Mac[N+1]=(Machine){D+1,0,0,0};
        sort(Mac,Mac+N+2);
        CDQ(0,N+1);
        printf("Case %lld: %lld\n",++kase,(long long)dp[N+1]);
    }
}