BZOJ_4311_向量_CDQ分治+线段树按时间分治
Description
你要维护一个向量集合，支持以下操作：
1.插入一个向量(x,y)
2.删除插入的第i个向量
3.查询当前集合与(x,y)点积的最大值是多少。如果当前是空集输出0
Input
第一行输入一个整数n，表示操作个数
接下来n行，每行先是一个整数t表示类型，如果t=1，输入向量
(x,y)；如果t=2，输入id表示删除第id个向量；否则输入(x,y)，查询
与向量(x,y)点积最大值是多少。
保证一个向量只会被删除一次，不会删没有插入过的向量
Output
对于每条t=3的询问，输出一个答案
Sample Input
5
1 3 3
1 1 4
3 3 3
2 1
3 3 3
1 3 3
1 1 4
3 3 3
2 1
3 3 3
Sample Output
18
15
15
HINT
n<=200000 1<=x,y<=10^6
Ans=x1*x+y1*y。
y1=-x/y *x1+Ans/y。
因为y是正数，也就是说我们只需要y轴正无穷的地方能看到的点。
于是维护上凸壳即可。
但是不会删除，考虑线段树按时间分治，对log个节点上用vector插入这个点。
然后[l,r]这段的询问向上找，在线段树的结点上用vector里的点更新答案。
可以预先把插入的点按横坐标排序，这样求凸壳就是O(n)的了。
并且询问也可以向上归并，时间复杂度O(nlogn)。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
int x=0; char s=nc();
while(s<'0'||s>'9') s=nc();
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
typedef long long ll;
typedef double f2;
#define ls p<<1
#define rs p<<1|1
#define N 200050
struct Point {
ll x,y;
Point() {}
Point(ll x_,ll y_) :
x(x_),y(y_) {}
};
struct A {
Point p;
int bg,ed;
bool operator < (const A &u) const {
return p.x<u.p.x;
}
}P[N];
f2 Slp(const Point &p1,const Point &p2) {
if(p1.x==p2.x) return p2.y>p1.y?1e18:-1e18;
return 1.0*(p2.y-p1.y)/(p2.x-p1.x);
}
ll f[N];
f2 qk[N];
ll qx[N],qy[N];
vector<Point>V[N<<2];
int n,m,id,t[N],tmp[N];
Point S[N];
void update(int l,int r,int x,int y,int p,Point pp) {
if(x<=l&&y>=r) {
V[p].push_back(pp); return ;
}
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,y,ls,pp);
if(y>mid) update(mid+1,r,x,y,rs,pp);
}
Point pp;
void solve(int l,int r,int p) {
int i,lim;
if(l==r) {
lim=V[p].size();
for(i=0;i<lim;i++) {
pp=V[p][i];
f[l]=max(f[l],pp.x*qx[l]+pp.y*qy[l]);
}
return ;
}
int mid=(l+r)>>1;
solve(l,mid,ls); solve(mid+1,r,rs);
int j=l,k=mid+1; i=l;
while(j<=mid&&k<=r) {
if(qk[t[j]]>=qk[t[k]]) tmp[i++]=t[j++];
else tmp[i++]=t[k++];
}
while(j<=mid) tmp[i++]=t[j++];
while(k<=r) tmp[i++]=t[k++];
for(i=l;i<=r;i++) t[i]=tmp[i];
lim=V[p].size();
if(lim==0) return ;
int top=0;
for(i=0;i<lim;i++) {
pp=V[p][i];
while(top>1&&Slp(S[top-1],S[top])<=Slp(S[top-1],pp)) top--;
S[++top]=pp;
}
j=1;
for(i=l;i<=r;i++) {
while(j<top&&Slp(S[j],S[j+1])>=qk[t[i]]) j++;
f[t[i]]=max(f[t[i]],qx[t[i]]*S[j].x+qy[t[i]]*S[j].y);
}
}
int main() {
// freopen("tt.in","r",stdin);
// freopen("tt.out","w",stdout);
n=rd();
int opt,i,x,y;
for(i=1;i<=n;i++) {
opt=rd();
if(opt==1) {
x=rd(); y=rd();
P[++id].p=Point(x,y);
P[id].bg=m+1;
}else if(opt==2) {
x=rd();
P[x].ed=m;
if(!m) P[x].ed=-1;
}else {
m++; x=rd(); y=rd();
qk[m]=(-1.0*x/y);
qx[m]=x; qy[m]=y;
}
}
sort(P+1,P+id+1);
for(i=1;i<=id;i++) {
if(P[i].bg<=m&&P[i].ed!=-1) {
P[i].ed=P[i].ed?P[i].ed:m;
update(1,m,P[i].bg,P[i].ed,1,P[i].p);
}
// printf("%d %d\n",P[i].bg,P[i].ed);
}
for(i=1;i<=m;i++) t[i]=i;
solve(1,m,1);
for(i=1;i<=m;i++) printf("%lld\n",f[i]);
}