https://www.lydsy.com/JudgeOnline/problem.php?id=3165
https://www.luogu.org/problemnew/show/P4097
要求在平面直角坐标系下维护两个操作：
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。
李超线段树板子题，参考代码：https://zepto.blog.luogu.org/solution-p4097
李超线段树参考：https://blog.csdn.net/flere825/article/details/76283734
参考代码还是很清新的。
#include<map> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<cctype> #include<vector> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef double dl; const int N=40010; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct node{ int l,r,id; dl yl,yr; node(int x1=0,int y1=0,int x2=0,int y2=0,int i=0){ l=x1,r=x2;yl=y1,yr=y2;id=i; if(l==r)yl=yr=max(yl,yr); } dl k(){return (yr-yl)/(r-l);} dl point(int x){return l==r?yl:yl+k()*(x-l);} void lm(int x){yl=point(x),l=x;} void rm(int x){yr=point(x),r=x;} }tr[N*4]; int lastans,n; node maxn(node a,node b,int k){ dl y1=a.point(k),y2=b.point(k); if(y1==y2)return a.id<b.id?a:b; return y1>y2?a:b; } node query(int a,int l,int r,int k){ if(l==r)return tr[a]; int mid=(l+r)>>1;node ans; if(k<=mid)ans=query(a<<1,l,mid,k); else ans=query(a<<1|1,mid+1,r,k); return maxn(ans,tr[a],k); } void upt(int a,int l,int r,node k){ if(k.l<l)k.lm(l); if(r<k.r)k.rm(r); int mid=(l+r)>>1; if(maxn(k,tr[a],mid).id==k.id)swap(k,tr[a]); if(min(tr[a].yl,tr[a].yr)>=max(k.yl,k.yr))return; if(l==r)return; if(tr[a].k()>k.k())upt(a<<1,l,mid,k); else upt(a<<1|1,mid+1,r,k); } void insert(int a,int l,int r,node k){ if(r<k.l||k.r<l)return; if(k.l<l)k.lm(l); if(r<k.r)k.rm(r); if(k.l==l&&r==k.r){ upt(a,l,r,k); return; } if(l==r)return; int mid=(l+r)>>1; insert(a<<1,l,mid,k);insert(a<<1|1,mid+1,r,k); } inline int num(int p){ return (read()+lastans-1)%p+1; } int main(){ n=read();int id=0; while(n--){ int op=read(); if(op==0){ int k=num(39989); printf("%d ",lastans=query(1,1,39989,k).id); }else{ int x0=num(39989),y0=num(1e9); int x1=num(39989),y1=num(1e9); if(x0>x1)swap(x0,x1),swap(y0,y1); node k=node(x0,y0,x1,y1,++id); insert(1,1,39989,k); } } return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++