线段树优化凸壳

Lena and Queries

题目链接:http://codeforces.com/contest/678/problem/F

三种操作,1.插入一个点(x,y)(x,y) 2.删除之前第ii个操作插入的点 3.给一个qq,询问在已有点中qx+yqx+y最大是多少

如果没有删除完全可以cdq分治然后在上凸壳上三分。有删除操作的话因为贡献不独立,所以不能cdq分治。

但是可以用上一次线段树优化建图一样的技巧,按时间来看,因为每个点的存在是一段区间,那么就可以用线段树拆成log个区间,然后把点“打”在上面(加进vector),最后对于线段树上每个区间,做凸壳然后询问就行了。每个询问会被问log次,所以时间复杂度粗略算有O(nlog2n)O(nlog^2n)

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300010
const ll NINF=1LL<<63;
struct Point
{
ll x,y;
Point(){}
Point(ll x_,ll y_)
{
x=x_;
y=y_;
}
Point operator -(const Point &t)const
{
return Point(x-t.x,y-t.y);
}
ll operator *(const Point &t)const
{
return x*t.x+y*t.y;
}
ll operator ^(const Point &t)const
{
return x*t.y-t.x*y;
}
bool operator <(const Point &t)const
{
return x<t.x||(x==t.x && y<t.y);
}
} p[N],res[N];
vector<Point> v[N<<2];
int opt[N];
bool del[N],emp[N];
int n,top;
ll ans[N];
void insert(int o,int l,int r,int ql,int qr,int x)
{
if(ql<=l && r<=qr)
{
v[o].push_back(p[x]);
return;
}
int mid=l+r>>1;
if(ql<=mid) insert(o<<1,l,mid,ql,qr,x);
if(mid<qr) insert(o<<1|1,mid+1,r,ql,qr,x);
}
void ask(int o)
{
int l=1,r=top;
while(r-l>=3)
{
int x=(l*2+r)/3;
int y=(l+2*r)/3;
if(p[o]*res[x]<p[o]*res[y]) l=x;
else r=y;
}
for(int i=l;i<=r;++i)
ans[o]=max(ans[o],p[o]*res[i]);
}
void solve(int o,int l,int r)
{
if(l<r)
{
int mid=l+r>>1;
solve(o<<1,l,mid);
solve(o<<1|1,mid+1,r);
}
sort(v[o].begin(),v[o].end());
top=0;
//cout<<o<<" "<<l<<" "<<r<<" "<<v[o].size()<<endl;
for(int i=0;i<v[o].size();++i)
{
while(top>1 && ((res[top]-res[top-1])^(v[o][i]-res[top]))>=0) --top;
res[++top]=v[o][i];
}
for(int i=l;i<=r;++i)
if(opt[i]==3 && !emp[i])
{
//cout<<"ask"<<endl;
ask(i);
//cout<<ans[i]<<endl;
}
}
int main()
{
scanf("%d",&n);
int cnt=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&opt[i]);
if(opt[i]==1)
{
scanf("%lld%lld",&p[i].x,&p[i].y);
++cnt;
}
else if(opt[i]==2)
{
int x;
scanf("%d",&x);
del[x]=true;
--cnt;
insert(1,1,n,x,i-1,x);
}
else
{
scanf("%lld",&p[i].x);
p[i].y=1;
if(cnt==0) emp[i]=true;
}
}
for(int i=1;i<=n;++i)
if(opt[i]==1 && !del[i])
insert(1,1,n,i,n,i);
for(int i=1;i<=n;++i) ans[i]=NINF;

solve(1,1,n);
for(int i=1;i<=n;++i)
if(opt[i]==3)
{
if(emp[i]) printf("EMPTY SET\n");
else printf("%lld\n",ans[i]);
}
return 0;
}
/*
3
1 -1 0
1 -1 1
3 -2
*/

线段树优化凸壳
https://izard.space/2018/10/09/线段树优化凸壳/
作者
forever_you
发布于
2018年10月9日
许可协议