前言
T4正解李超线段树?不会,滚过来学
保留节目百度百科自学已被删除
讲解
貌似思路并不是很难的亚子
我们需要在线支持一下两个操作:
-
插入一条线段
-
给定\(x_0\),询问当\(x=x_0\)时所有线段的最高点
我们可以使用权值线段树!
对于每个区间,我们维护一个最优线段
1.插入
显然对于一个线段完全覆盖的区间我们才处理
分四种情况讨论:
(1).当前区间无最优线段
直接赋值
(2).当前线段完全覆盖最优线段
直接赋值
(3).当前线段完全被最优线段覆盖
直接滚粗
(4).相交
最复杂的情况,我们考虑将覆盖该区间最长的线段保留为最优线段
欸嘿?怎么搞呢?其实只需判断该区间中点谁在上面就行了,中点位置在上面的线段一定是覆盖最长的线段
然后把另外一条丢到下面去接着修改
插入时间复杂度\(O(\log^2 n)\)
2.询问
一直往下走,对于每个走到的区间的最优线段求出一个函数值,取\(\texttt{max}\)即可
询问时间复杂度\(O(\log n)\)
练习
代码
「雅礼集训 2017 Day2」线段游戏
const int M = 1000001;
const int MAXN = 2000005;
int n,Q;
struct line
{
double k,b;
bool f;
line(){}
line(double k1,double b1,bool f1){
k = k1;
b = b1;
f = f1;
}
};
#define lc (x<<1)
#define rc (x<<1|1)
double getf(line w,int x){return w.k * x + w.b;}
struct LiChaoSegmentTree
{
line t[MAXN << 2];
void Add(int x,int l,int r,int ql,int qr,line w)
{
int mid = (l+r) >> 1;
if(ql <= l && r <= qr)
{
if(!t[x].f) t[x] = w;
else if(getf(w,l) >= getf(t[x],l) && getf(w,r) >= getf(t[x],r)) t[x] = w;
else if(getf(w,l) <= getf(t[x],l) && getf(w,r) <= getf(t[x],r)) return;
else
{
if(getf(w,mid) >= getf(t[x],mid)) swap(w,t[x]);
if(getf(w,l) > getf(t[x],l)) Add(lc,l,mid,ql,qr,w);
else Add(rc,mid+1,r,ql,qr,w);
}
return;
}
if(ql <= mid) Add(lc,l,mid,ql,qr,w);
if(mid+1 <= qr) Add(rc,mid+1,r,ql,qr,w);
}
double Query(int x,int l,int r,int q)
{
double ret = -M;
if(l <= q && q <= r && t[x].f) ret = getf(t[x],q);
if(l == r) return ret;
int mid = (l+r) >> 1;
if(q <= mid) ret = Max(ret,Query(lc,l,mid,q));
else ret = Max(ret,Query(rc,mid+1,r,q));
return ret;
}
}st;
void AddLine()
{
int x1 = Read() + M,y1 = Read(),x2 = Read() + M,y2 = Read();
double k,b;
if(x1 == x2) k = 0,b = Max(y1,y2);
else k = 1.0 * (y2-y1) / (x2-x1),b = y1 - k * x1;
st.Add(1,1,M<<1,Min(x1,x2),Max(x1,x2),line(k,b,1));
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); Q = Read();
for(int i = 1;i <= n;++ i) AddLine();
for(; Q ;-- Q)
{
int opt = Read();
if(!opt) AddLine();
else
{
double ans = st.Query(1,1,M<<1,Read()+M);
if(ans == -M) Put(0,'\n');
else printf("%.2f\n",ans);
}
}
return 0;
}