月赛的题目没什么好说的，今天主要学了李超线段树
模板：P忘记了，见洛谷
原理：
线段树的每一个节点贮存当前的区间中点y坐标最大的线段（称为优势线段），查找x=k的最大y坐标时遍历所有含有x的区间
对于新插入的线段，先找到其完全覆盖的区间(logn)
对于每一个区间，如果没有优势线段就直接插入，然后退出（这是标记永久化的体现，每次查询都要记录路径上的所有答案，所以可以直接弹出，不用修改子结点）
若原有优势线段，先把中点y坐标大的设为当前结点优势线段，考虑另一个线段
（1）若另一个线段两个端点都小于优势线段，则对这个区间不再可能有贡献，直接return
（2）若左端点大于优势线段，则交点在左边，则当前线段对左子树可能有贡献，递归左子树
（3）若右端点大于优势线段，同理递归柚子树
很明显这两种情况不会同时出现
正确性：很显然，最大的值一定会在这些线段中出现
总结：实际上就是对于每一个x=k，储存其可能的logn个答案，以中点坐标为判断条件可以使得一个线段只对一半区间有贡献，避免大量重复计算
#include<bits/stdc++.h>
using namespace std;
const long long mod=39989,mod2=1e9+1;
const double eps=1e-12;
long long T,lans,op,x0,yo,x1,yl,cnt,ls;
struct ss
{
double k,b;
long long l,r;
}ed[400005];
void add()
{
cnt++;
if(x0==x1)
{
ed[cnt].l=ed[cnt].r=x0;
ed[cnt].k=0;
ed[cnt].b=max(yo,yl);
}
else
{
ed[cnt].l=x0;
ed[cnt].r=x1;
ed[cnt].k=(double)(yl-yo)*1.000/(double)(x1-x0);
ed[cnt].b=yo*1.000-x0*ed[cnt].k;
}
return;
}
struct sd
{
long long l,r;
long long sid;
}tr[1000005];
double cacl(long long id,long long pos)
{
return ed[id].k*pos+ed[id].b;
}
long long cmp(double aa,double bb)
{
if(fabs(bb-aa)<=eps) return 0;
if(aa-bb>eps) return 1;
return -1;
}
void upd(long long pos,long long id)
{
int mid=(tr[pos].l+tr[pos].r)/2;
if(tr[pos].sid==0)
{
tr[pos].sid=id;
return ;
}
long long fl=cmp(cacl(id,mid),cacl(tr[pos].sid,mid));
if(fl==1||(fl==0&&id<tr[pos].sid))
{
swap(id,tr[pos].sid);
}
if(tr[pos].l==tr[pos].r) return ;
fl=cmp(cacl(id,tr[pos].l),cacl(tr[pos].sid,tr[pos].l));
if(fl==1||(fl==0&&id<tr[pos].sid))
{
upd(pos*2,id);
return ;
}
fl=cmp(cacl(id,tr[pos].r),cacl(tr[pos].sid,tr[pos].r));
if(fl==1||(fl==0&&id<tr[pos].sid))
{
upd(pos*2+1,id);
return ;
}
return ;
}
void update(long long pos,long long l,long long r,long long id)
{
if(tr[pos].r<l||tr[pos].l>r) return ;
if(tr[pos].l>=l&&tr[pos].r<=r)
{
upd(pos,id);
return ;
}
update(pos*2,l,r,id);
update(pos*2+1,l,r,id);
}
void build(long long pos,long long l,long long r)
{
tr[pos].l=l;
tr[pos].r=r;
if(l==r) return ;
build(pos*2,l,(l+r)/2);
build(pos*2+1,(l+r)/2+1,r);
}
void query(long long id,long long k)
{
if(tr[id].l>k||tr[id].r<k) return ;
long long fl=cmp(cacl(tr[id].sid,k),cacl(lans,k));
if(fl==1||(fl==0&&tr[id].sid<lans))
{
lans=tr[id].sid;
}
if(tr[id].l==tr[id].r) return ;
query(id*2,k);
query(id*2+1,k);
}
int main()
{
build(1,1,mod);
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&op);
if(op==0)
{
scanf("%lld",&x0);
x0=(x0+lans-1)%mod+1;
lans=0;
query(1,x0);
printf("%lld\n",lans);
}
else
{
scanf("%lld%d%d%d",&x0,&yo,&x1,&yl);
x0=(x0+lans-1)%mod+1;
x1=(x1+lans-1)%mod+1;
yo=(yo+lans-1)%mod2+1;
yl=(yl+lans-1)%mod2+1;
if(x0>x1) swap(x0,x1),swap(yo,yl);
add();
update(1,x0,x1,cnt);
}
}
return 0;
}