BZOJ原题地址
洛谷原题地址
思路
可以用线段树很方便地维护，对于每个区间，如果要加地线段在中点处更优，就替换原有的线段。
对于每条新加入的线段，我们需要用$log(n)$ 的复杂度将它分配到不同的区间内，对于每个区间，又要用$log(n)$的复杂度判断在所有子区间的优劣程度。
所以，插入复杂度是$log^2(n)$的，查询复杂度依然为$log(n)$。
代码实现
使用结构体$Node$存储每条线段的信息。
对于一条编号为$id$的线段，它的左端点是$(l,yl)$，而右端点是$(r,yr)$。判断交点的存在性和位置时，我们使用$Node.k$来获取这条线段的斜率。
在插入时，我们会不断调整新线段的左右端点位置以确保被当前区间覆盖，使用$Node.lm()$ / $Node.rm()$ 实现这个操作。
对于斜率不存在的线段要简单地特殊处理一下，我的插入方法能规避很多特判。
细节见注释。
#include
#define ls (p<<1)
#define rs (p<<1|1)
#define maxn 100001
#define mid ((l+r)>>1)
using namespace std;
struct Node{
int l,r,id;
double 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);
}
double get(int x){return l==r?yl:yl+(k()*(x-l));}
double k(){return (yr-yl)/(r-l);}
void lm(int x){yl=get(x);l=x;}
void rm(int x){yr=get(x);r=x;}
};
bool hei(Node a,Node b,int x){
return a.get(x)==b.get(x)?a.idb.get(x);
}
struct St{
Node tree[maxn*4];
void build(int l,int r,int p){
tree[p].l=l,tree[p].r=r;
if (l==r) return;
build(l,mid,ls);
build(mid+1,r,rs);
}
Node query(int t,int l,int r,int p){
if (l==r) return tree[p];Node tem;
if (t<=mid) tem=query(t,l,mid,ls);
else tem=query(t,mid+1,r,rs);
return hei(tem,tree[p],t)?tem:tree[p];
}
void update(int l,int r,Node k,int p){
if (tree[p].l>k.l) k.lm(tree[p].l);
if (tree[p].r=max(k.yl,k.yr)) return;//如果在当前区间内没有交点就直接return
if (l==r) return;
if (tree[p].k()<=k.k()) update(mid+1,r,k,rs);//判断交点的位置
else update(l,mid,k,ls);
}
void insert(int l,int r,Node k,int p){
if (k.l>r||k.rk.l) k.lm(tree[p].l);
if (tree[p].r>m;
while(m--){
int temp;cin>>temp;
if (!temp){
int k;cin>>k;
k=(k+la-1)%39989+1;
la=T.query(k,1,n,1).id;
cout<>x0>>y0>>x1>>y1;
x0=(x0+la-1)%39989+1;x1=(x1+la-1)%39989+1;
y0=(y0+la-1)%1e9+1;y1=(y1+la-1)%1e9+1;//注意是1e9，而非题目所述的109
if (x0>x1) swap(x0,x1),swap(y0,y1);
Node tem=Node(x0,y0,x1,y1,++Ind);
T.insert(1,n,tem,1);
}
}
}