算法介绍：
李超线段树是一种用于维护平面直角坐标系内线段（直线）关系的数据结构。
它常被用来处理这样一种形式的问题：
给定一个平面直角坐标系，支持动态插入一条线段（直线），询问从某一个位置横坐标x从上向下能看到的最高的
一条线段（也就是给一条竖线，问这条竖线与所有线段的最高的交点。）
主要思想：
对整个横坐标建线段树，每个节点的值存的是一条直线的编号。
要求这条直线在横坐标为mid的时候纵坐标最大。
插入：
如果是叶子节点，我们直接保留最大的。
先比较斜率，再比较横坐标为mid时的纵坐标。
如果新线段的斜率大，并且横坐标为mid时的纵坐标大，那么把原线段下放左区间，节点值改为x
如果新线段的斜率大，但是横坐标为mid时的纵坐标小，那么把新线段下放右区间，不更改节点值
如果新线段的斜率小，但是横坐标为mid时的纵坐标大，那么把原线段下放右区间，节点值改为x
如果新线段的斜率小，并且横坐标为mid时的纵坐标小，那么把新线段下放左区间，不更改节点值
double f(int w,int x)
{
return k[w]*(x-1)+b[w];
}
void change(int nod,int l,int r,int x)
{
if(l==r)
{
if(f(x,l)>f(tree[nod],l))tree[nod]=x;
return;
}
int mid=(l+r)/2;
if(k[tree[nod]]<k[x])
{
if(f(x,mid)>f(tree[nod],mid))
{
change(nod*2,l,mid,tree[nod]);
tree[nod]=x;
}
else change(nod*2+1,mid+1,r,x);
}
if(k[tree[nod]]>k[x])
{
if(f(x,mid)>f(tree[nod],mid))
{
change(nod*2+1,mid+1,r,tree[nod]);
tree[nod]=x ;
}
else change(nod*2,l,mid,x) ;
}
} 查询：
如果是叶子节点直接返回横坐标的值。
如果查询区间在左区间，返回当前的节点的横坐标的值 和 左区间的值 的最大值
如果查询区间在右区间，返回当前的节点的横坐标的值 和 右区间的值 的最大值
double query(int nod,int l,int r,int x)
{
if(l==r)return f(tree[nod],x);
int mid=(l+r)/2;
if(x<=mid)return max(f(tree[nod],x),query(nod*2,l,mid,x));
else return max(f(tree[nod],x),query(nod*2+1,mid+1,r,x));
} 例题：
1.P4254 [JSOI2008]Blue Mary开公司
题意：
有两种操作：
1.给你一条一次函数
2.给你一个x，让你求所有函数中最大的y
现在有n个操作，要求你对每一个操作2 输出最大的y值/100的结果
题解：
这是李超线段树裸题，套用上面写的板子就能A了。
只要插入和查询两个操作即可。
代码：
#include
using namespace std;
const int N=500005;
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return -ret;return ret;
}
int n,m,tree[N*4];
double k[N*2],b[N*2];
char s[20];
double f(int w,int x)
{
return k[w]*(x-1)+b[w];
}
void change(int nod,int l,int r,int x)
{
if(l==r)
{
if(f(x,l)>f(tree[nod],l))tree[nod]=x;
return;
}
int mid=(l+r)/2;
if(k[tree[nod]]<k[x])
{
if(f(x,mid)>f(tree[nod],mid))
{
change(nod*2,l,mid,tree[nod]);
tree[nod]=x;
}
else change(nod*2+1,mid+1,r,x);
}
if(k[tree[nod]]>k[x])
{
if(f(x,mid)>f(tree[nod],mid))
{
change(nod*2+1,mid+1,r,tree[nod]);
tree[nod]=x ;
}
else change(nod*2,l,mid,x) ;
}
}
double query(int nod,int l,int r,int x)
{
if(l==r)return f(tree[nod],x);
int mid=(l+r)/2;
if(x<=mid)return max(f(tree[nod],x),query(nod*2,l,mid,x));
else return max(f(tree[nod],x),query(nod*2+1,mid+1,r,x));
}
int main()
{
n=read();
while(n--)
{
scanf("%s",s);
if(s[0]=='P')
{
m++;
scanf("%lf%lf",&b[m],&k[m]);
change(1,1,N,m);
}
else{
int x=read();
printf("%d\n",(int)(query(1,1,N,x)/100));
}
}
return 0;
} 2.P4097 [HEOI2013]Segment
题目：
要求在平面直角坐标系下维护两个操作：
1. 在平面上加入一条线段。记第 i 条被插入的线段的标号为 i
2. 给定一个数 k,询问与直线 x = k 相交的线段中，交点最靠上的线段的编号。
题解;
这题和上一题的区别就是，这题是线段，上一题是直线。
线段要复杂很多，要把线段割成一段一段的。
修改还时比较是y轴的坐标。
#include
using namespace std;
#define mid (l+r)/2
const int N=100005;
int n,m,lastans;
struct node{
int l,r,id;
double yl,yr;
void Node(int x=0,int y=0,int xx=0,int yy=0,int i=0)
{
l=x,r=xx,yl=y,yr=yy,id=i;
if(l==r)yl=yr=max(yl,yr);
}
double k(){return (yr-yl)/(r-l);}//斜率
double get(int x){return l==r?yl:yl+(k()*(x-l));}//于直线x的交点
void lm(int x){yl=get(x);l=x;}
void rm(int x){yr=get(x);r=x;}
}tree[N*4];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return -ret;return ret;
}
bool bj(node a,node b,int x)
{
return a.get(x)==b.get(x)?a.idb.get(x);
}
void build(int nod,int l,int r)
{
tree[nod].l=l,tree[nod].r=r;
if(l==r)return;
build(nod*2,l,mid);
build(nod*2+1,mid+1,r);
}
void change(int nod,int l,int r,node k)
{
if(tree[nod].l>k.l)k.lm(tree[nod].l);
if(tree[nod].r<k.r)k.rm(tree[nod].r);
if(bj(k,tree[nod],mid))swap(tree[nod],k);
if(min(tree[nod].yl,tree[nod].yr)>=max(k.yl,k.yr))return;//没有交点
if(l==r)return;
if(tree[nod].k()<=k.k())change(nod*2+1,mid+1,r,k);
else change(nod*2,l,mid,k);
}
void insert(int nod,int l,int r,node k)
{
if(k.l>r||k.r<l)return;
if(tree[nod].l>k.l)k.lm(tree[nod].l);
if(tree[nod].r<k.r)k.rm(tree[nod].r);
if(l==k.l&&r==k.r)
{
change(nod,l,r,k);
return;
}
if(l==r)return;
insert(nod*2,l,mid,k);
insert(nod*2+1,mid+1,r,k);
}
node query(int nod,int l,int r,int x)
{
if(l==r)return tree[nod];
node xu;
if(x<=mid)xu=query(nod*2,l,mid,x);
else xu=query(nod*2+1,mid+1,r,x);
return bj(xu,tree[nod],x)?xu:tree[nod];
}
int main()
{
n=read();
build(1,1,40000);
while(n--)
{
int opt=read();
if(opt==1)
{
int x=read(),y=read(),xx=read(),yy=read();
x=(x+lastans-1)%39989+1;
y=(y+lastans-1)%1000000000 +1;
xx=(xx+lastans-1)%39989+1;
yy=(yy+lastans-1)%1000000000 +1;
if(x>xx)swap(x,xx),swap(y,yy);
node xu;
xu.Node(x,y,xx,yy,++m);
insert(1,1,40000,xu);
}
else{
int x=read();
x=(x+lastans-1)%39989+1;
lastans=query(1,1,40000,x).id;
printf("%d\n",lastans);
}
}
return 0;
} 
京公网安备 11010502036488号