P4097 【模板】李超线段树 / [HEOI2013] Segment
强制在线，那么这种问题该如何解决？
我们可以把任务转化为维护如下操作：
- 加入一个一次函数
- 给定 \(k\)，求定义域包含 \(k\) 的所有一次函数中，在 \(k\) 处取值最大的那个，如果有多个函数取值相同，选编号最小的。
注意：有可能线段斜率不存在
看到区间修改，我们按照线段树解决区间问题的常见方法，给每个节点一个懒标记。标记 \(l_i\)表示用 \(l_i\) 修改这个区间。
现在我们需要插入一条线段 \(f_i\)，考虑一个被 \(f_i\) 完整覆盖的线段树区间。若该区间没有标记，就直接标记，否则就递归下传标记。
设该区间原本线段为 \(g_i\)，把该区间根据 \(f_i\)是否大于 \(g_i\) 分为两个子区间，其中肯定有一个子区间被左区间或右区间完全包含。
也就是说，在两条线段中，肯定有一条线段，只可能成为左区间的答案，或者只可能成为右区间的答案。我们用这条线段递归更新对应子树，用另一条线段作为懒标记更新整个区间，这就保证了递归下传的复杂度。当一条线段只可能成为左或右区间的答案时，才会被下传，所以不用担心漏掉某些线段。
具体来说，当前区间的终点为 \(mid\)，如果 \(f(mid)>g(mid)\)，交换 \(f\) 和 \(g\)。
当 \(f\) 中点劣于 \(g\) 时 ：
- 在左端点时 \(f\) 优于 \(g\) 那么 \(f\) 和 \(g\) 的交点一定在左区间，\(f\) 只可能在左区间才能优于 \(g\)，递归左区间。
- 在右端点时 \(f\) 优于 \(g\) 那么 \(f\) 和 \(g\) 的交点一定在右区间，\(f\) 只可能在右区间才能优于 \(g\)，递归右区间。
- 若在左右区间都是 \(g\) 更优，那么不需要下传。
其实对每个区间都用一条最优的线段表示，如果你加入的线段劣于该线段
就判断在那个区间可以更优。
至于查询，可以到达的所有线段取最大值就行了。
int n,last;
struct line{
ldb k,b;
}p[N];
int cnt;
inline void add(int x0, int y0, int x1, int y1) {
cnt++;
if(x0==x1)p[cnt].k=0,p[cnt].b=max(y0, y1);
else p[cnt].k=1.0*(y1-y0)/(x1-x0),p[cnt].b=y0-p[cnt].k*x0;
}
int s[N];
inline ldb calc(int id,int d) { return p[id].b+p[id].k*d;}
inline int cmp(ldb x,ldb y) {
if(x-y>eps)return 1;
if(y-x>eps)return -1;
return 0;
}
inline void change(int k,int l,int r,int u){
int &v=s[k],mid=(l+r)>>1;
int bmid=cmp(calc(u,mid),calc(v,mid));
if(bmid==1||(!bmid&&u<v))swap(u,v);
int bl=cmp(calc(u,l),calc(v,l)),br=cmp(calc(u,r),calc(v,r));
if(bl==1||(!bl&&u<v))change(lc,l,mid,u);
if(br==1||(!br&&u<v))change(rc,mid+1,r,u);
}
inline void insert(int k,int tl,int tr,int l,int r,int u){
if(l<=tl&&tr<=r) {
change(k,tl,tr,u);
return;
}
int mid=(tl+tr)>>1;
if(l<=mid)insert(lc,tl,mid,l,r,u);
if(mid<r)insert(rc,mid+1,tr,l,r,u);
}
inline pdi pmax(pdi x,pdi y){
if(cmp(x.fi,y.fi)==-1)return y;
else if(cmp(x.fi,y.fi)==1)return x;
return x.se<y.se?x:y;
}
inline pdi ask(int k,int l,int r,int d){
if(l==r)return {calc(s[k],d),s[k]};
int mid=(l+r)>>1;
pdi res={calc(s[k],d),s[k]};
if(mid>=d)res=pmax(res,ask(lc,l,mid,d));
else res=pmax(res,ask(rc,mid+1,r,d));
return res;
}
signed main(){
n=read();
int op,k,x0,y0,x1,y1;
up(i,1,n){
op=read();
if(op==1){
x0=(read()+last-1+mod1)%mod1+1;
y0=(read()+last-1+mod2)%mod2+1;
x1=(read()+last-1+mod1)%mod1+1;
y1=(read()+last-1+mod2)%mod2+1;
if (x0>x1)swap(x0,x1),swap(y0,y1);
add(x0,y0,x1,y1);
insert(1,1,mod1,x0,x1,cnt);
}
else {
k=read();
k=(k+last-1+mod1)%mod1+1;
last=ask(1,1,mod1,k).second;
cout<<(last)<<endl;
}
}
return 0;
}