李超线段树
一，问题背景
要求在平面直角坐标系上维护 \(n\) 个操作，操作有如下两种（强制在线）：
在平面上加入一条线段，给出两端点横纵坐标 \((x_0,y_0)\)，\((x_1,y_1)\)。
给定一个横坐标的值 \(k\)，求当 \(x=k\) 时平面中使得 \(y\) 最大的直线的编号（若有多条取编号最小的），若不存在，输出 \(0\)。
数据范围：\(1\leq n\leq 10^5\)，\(1\leq k\), \(x_0\), \(x_1\leq 4\times 10^4\)，\(1\leq y_0\), \(y_1\leq 10^9\)。
分析：在这样一个问题中，操作一相当于对一段区间进行修改，操作二相当于对某一点进行查询，容易想到线段树。由于我们只关心最优解，所以在插入线段时，如果它比原来的线段更优，我们便不再需要记录原来的线段了，所以在线段树中记录每个区间中有可能成为最优解的线段即可。
二，实现过程
首先对于区间修改，按线段树问题的常用方法，可以给每个结点打一个懒标记，每个结点的懒标记都是一条线段，包含斜率和截距。
现在考虑插入线段 \(f\) 的过程：
如果当前区间没有被任何一条线段覆盖，直接修改。
比较端点，如果新线段被原有线段完全覆盖，直接返回。
比较端点，如果新线段可完全覆盖原有线段，直接修改。
通过区间中点大小和端点值大小判断新旧线段覆盖的长度关系，覆盖长度长的记录在该结点，短的由于只覆盖了左区间或右区间的一部分，可以递归入左或右子树。
现在考虑单点查询的过程：
对于给定的横坐标，将递归子区间过程中所经过的每一条被记录的线段都拿出来比较。
为什么要全部比较
在插入线段的过程中，我们发现标记之间很难合并，所以采用的是标记永久化策略，所以在单点查询递归子区间的过程中要取出所有经过区间的标记。
参考代码
变量声明： 1
2
3
4
5
6
7
8
9
using namespace std;
double const eps=1e-9;
int const mod1=39989,mod2=1e9;
int n,t,op,X0,X1,Y0,Y1,lst,tr[200005];
struct line {double k,b;} l[100005];
下传标记： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15inline int cmp(double x,double y)
{
if(x-y>eps) return 1;
if(y-x>eps) return -1;
return 0;
}
...
void update(int rt,int l,int r,int x)
{
int &y=tr[rt],mid=(l+r)/2;
if(cmp(Y(x,mid),Y(y,mid))==1) swap(x,y);
int cl=cmp(Y(x,l),Y(y,l)),cr=cmp(Y(x,r),Y(y,r));
if(cl==1||(!cl&&x<y)) update(ls,l,mid,x);
if(cr==1||(!cr&&x<y)) update(rs,mid+1,r,x);
}
拆分线段： 1
2
3
4
5
6
7void change(int rt,int l,int r,int L,int R,int x)
{
if(l>R||r<L) return;
if(l>=L&&r<=R) {update(rt,l,r,x);return;}
int mid=(l+r)/2;
change(ls,l,mid,L,R,x),change(rs,mid+1,r,L,R,x);
}
单点查询： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15inline pr mx(pr x,pr y)
{
if(cmp(x.first,y.first)==1) return x;
if(cmp(x.first,y.first)==-1) return y;
return x.second<y.second?x:y;
}
...
pr query(int rt,int l,int r,int x)
{
if(x>r||x<l) return {0,0};
int mid=(l+r)/2;
double ret=Y(tr[rt],x);
if(l==r) return {ret,tr[rt]};
return mx({ret,tr[rt]},mx(query(ls,l,mid,x),query(rs,mid+1,r,x)));
}
完整代码： 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
using namespace std;
double const eps=1e-9;
int const mod1=39989,mod2=1e9;
int n,t,op,X0,X1,Y0,Y1,lst,tr[200005];
struct line {double k,b;} l[100005];
inline int cmp(double x,double y)
{
if(x-y>eps) return 1;
if(y-x>eps) return -1;
return 0;
}
inline pr mx(pr x,pr y)
{
if(cmp(x.first,y.first)==1) return x;
if(cmp(x.first,y.first)==-1) return y;
return x.second<y.second?x:y;
}
inline double Y(int i,int x)
{
return l[i].k*x+l[i].b;
}
inline void newline(int X0,int Y0,int X1,int Y1)
{
++t;
if(X0==X1) l[t].k=0,l[t].b=max(Y0,Y1);
else l[t].k=(Y1-Y0)*1.0/(X1-X0),l[t].b=Y0-l[t].k*X0;
}
void update(int rt,int l,int r,int x)
{
int &y=tr[rt],mid=(l+r)/2;
if(cmp(Y(x,mid),Y(y,mid))==1) swap(x,y);
int cl=cmp(Y(x,l),Y(y,l)),cr=cmp(Y(x,r),Y(y,r));
if(cl==1||(!cl&&x<y)) update(ls,l,mid,x);
if(cr==1||(!cr&&x<y)) update(rs,mid+1,r,x);
}
void change(int rt,int l,int r,int L,int R,int x)
{
if(l>R||r<L) return;
if(l>=L&&r<=R) {update(rt,l,r,x);return;}
int mid=(l+r)/2;
change(ls,l,mid,L,R,x),change(rs,mid+1,r,L,R,x);
}
pr query(int rt,int l,int r,int x)
{
if(x>r||x<l) return {0,0};
int mid=(l+r)/2;
double ret=Y(tr[rt],x);
if(l==r) return {ret,tr[rt]};
return mx({ret,tr[rt]},mx(query(ls,l,mid,x),query(rs,mid+1,r,x)));
}
inline int rd()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
inline void wt(int x)
{
if(x>9) wt(x/10);
putchar(x%10+'0');
}
signed main()
{
n=rd();
for(int i=1;i<=n;i++)
{
op=rd();
if(op==1)
{
X0=rd(),Y0=rd(),X1=rd(),Y1=rd();
X0=(X0+lst-1+mod1)%mod1+1,X1=(X1+lst-1+mod1)%mod1+1;
Y0=(Y0+lst-1+mod2)%mod2+1,Y1=(Y1+lst-1+mod2)%mod2+1;
if(X0>X1) swap(X0,X1),swap(Y0,Y1);
newline(X0,Y0,X1,Y1),change(1,1,mod1,X0,X1,t);
}
else
{
X0=rd(),X0=(X0+lst-1+mod1)%mod1+1;
lst=query(1,1,mod1,X0).second;
wt(lst),putchar('\n');
}
}
return 0;
}