题目概述

HDU5127

解题报告

我们分析在甜度热爱为 $x$ ，酸度热爱为 $y(y>0)$ 时，$A(p_1,q_1),B(p_2,q_2)(p_1<p_2)$ 中 $A$ 比 $B$ 好的条件：

$$ p_1x+q_1y\ge p_2x+q_2y\\ x(p_1-p_2)\ge y(q_2-q_1)\\ {x\over y}\le {q_2-q_1\over p_1-p_2}\\ {q_2-q_1\over p_2-p_1}\le -{x\over y} $$

也就是说 $k_{AB}\le -{x\over y}$ 时，$A$ 比 $B$ 好。这意味着如果 $k_{AB}\le k_{BC}$ ，$B$ 是一定没有作用的（ $C$ 在 $B$ 右边）：

• 如果 $k_{BC}\le -{x\over y}$ ，则 $k_{AB}\le k_{BC}\le -{x\over y}$ ，$A$ 比 $B$ 好。
• 如果 $k_{BC}>-{x\over y}$ ，则 $C$ 比 $B$ 好。

由此可见，最优的答案只可能在上凸壳上（如果 $y<0$ ，那么答案在下凸壳上）。

所以我们只要能动态维护上凸壳和下凸壳，然后每次二分斜率就可以找到最优解。

然而动态凸包是不能删点的，但是可以通过倒过来加点的方式实现，因此考虑离线cdq分治，利用左半边的凸包来更新右半边的答案：

• 对于 $[L,mid]$ 中的加点操作，如果在 $[L,R]$ 出现过对应的删点操作，则不执行。
• 对于 $[mid+1,R]$ 中的删点操作，如果要删的点在 $[L,mid]$ 中，则倒着执行时改为加点操作。

为了记录斜率，维护凸壳的时候需要再开一个set存相邻两点之间的斜率，每次凸壳变化都需要找到前驱和后继并更新相邻斜率（或者手写平衡树，就不用写两个了QAQ）。

示例程序

#include<set>
#include<map>
#include<cstdio>
#include<algorithm>
#define X first
#define Y second
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;typedef long double DB;
typedef pair<int,int> vec;typedef pair<DB,vec> con;
const int maxn=50000;

int n,ti,vis[maxn+5];LL ans[maxn+5];
int lst[maxn+5];map<vec,int> ID;
struct data {int tp,x,y;} q[maxn+5];
set<vec> A,B;set<vec>::iterator L,R,pre,suf;
set<con> C,D;set<con>::iterator it;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline vec operator - (const vec &a,const vec &b) {return mp(b.X-a.X,b.Y-a.Y);}
inline LL Cross(const vec &a,const vec &b) {return (LL)a.X*b.Y-(LL)a.Y*b.X;}
bool check(set<vec> &s,vec a){
    L=s.lower_bound(a);if (L==s.end()) return false;
    if ((*L).X==a.X) return true;if (L!=s.begin() && (*--L).X==a.X) return false;
    if (a.X<(*L).X) return false;R=L;R++;return Cross(*R-*L,a-*L)<=0;
}
#define K(a,b) ((DB)((b).Y-(a).Y)/((b).X-(a).X))
void del(set<vec> &s,set<con> &t,set<vec>::iterator it){
    pre=it;suf=it;suf++;
    if (pre!=s.begin()) pre--,t.erase(mp(K(*pre,*it),*pre));
    if (suf!=s.end()) t.erase(mp(K(*it,*suf),*it));
    if ((*pre).X<(*it).X && suf!=s.end()) t.insert(mp(K(*pre,*suf),*pre));
    s.erase(it);
}
void ins(set<vec> &s,set<con> &t,vec a){
    suf=s.upper_bound(a);
    if (suf!=s.end()) t.insert(mp(K(a,*suf),a));
    if (suf!=s.begin()){
        pre=suf;pre--;
        if (suf!=s.end()) t.erase(mp(K(*pre,*suf),*pre));
        t.insert(mp(K(*pre,a),*pre));
    }
    s.insert(a);
}
void Insert(set<vec> &s,set<con> &t,vec a){
    if (check(s,a)) return;
    L=s.lower_bound(a);if (L!=s.begin() && (*--L).X==a.X) del(s,t,L);
    R=s.lower_bound(a);
    if (R!=s.begin() && (L=R,L--)!=s.begin())
        while (L!=s.begin()) {R=L;L--;if (Cross(*R-*L,a-*L)>=0) del(s,t,R);}
    L=s.lower_bound(a);
    if (L!=s.end() && (R=L,R++)!=s.end())
        while (R!=s.end()) {if (Cross(*L-*R,a-*R)<=0) del(s,t,L);L=R;R++;}
    ins(s,t,a);
}
void Update(int x,int y) {Insert(A,C,mp(x,y));Insert(B,D,mp(x,-y));}
LL Ask(set<vec> &s,set<con> &t,int x,int y){
    it=t.upper_bound(mp((DB)-x/y,mp(2e9,2e9)));
    if (it==t.begin()) return (LL)(*s.rbegin()).X*x+(LL)(*s.rbegin()).Y*y;
    it--;return (LL)(*it).sc.X*x+(LL)(*it).sc.Y*y;
}
LL Query(int x,int y){
    if (A.empty() && B.empty()) return -9e18;
    if (y==0) return x>0?(LL)(*A.rbegin()).X*x:(LL)(*A.begin()).X*x;
    if (y>0) return Ask(A,C,x,y);if (y<0) return Ask(B,D,x,-y);
}
void Solve(int L,int R){
    if (L==R) return; int mid=L+(R-L>>1);ti++;A.clear();B.clear();C.clear();D.clear();
    for (int i=L;i<=mid;i++) if (q[i].tp==-1) vis[lst[i]]=ti;
    for (int i=mid+1;i<=R;i++) if (q[i].tp==-1 && L<=lst[i] && lst[i]<=mid) vis[i]=vis[lst[i]]=ti;
    for (int i=L;i<=mid;i++) if (q[i].tp==1 && vis[i]<ti) Update(q[i].x,q[i].y);
    for (int i=R;i>mid;i--)
        if (q[i].tp==-1 && vis[i]==ti) Update(q[i].x,q[i].y); else
        if (q[i].tp==0) ans[i]=max(ans[i],Query(q[i].x,q[i].y));
    Solve(L,mid);Solve(mid+1,R);
}
int main(){
    freopen("5127.in","r",stdin);freopen("5127.out","w",stdout);
    for (readi(n);n;readi(n)){
        ID.clear();A.clear();B.clear();C.clear();D.clear();
        for (int i=1;i<=n;i++){
            readi(q[i].tp);readi(q[i].x);readi(q[i].y);ans[i]=-9e18;
            if (q[i].tp==1) ID[mp(q[i].x,q[i].y)]=i;
            if (q[i].tp==-1) lst[i]=ID[mp(q[i].x,q[i].y)];
        }
        Solve(1,n);for (int i=1;i<=n;i++) if (q[i].tp==0) printf("%lld\n",ans[i]);
    }
    return 0;
}