[HEOI2013]Segment
题目分析：
是李超线段树的板子题，在这里就稍微提一嘴李超线段树吧。
其实李超线段树就是用来解决插入线段，查询 \(x=k\) 时纵坐标的最大值的。
对于李超线段树就是标记永久化的思想，会对于每一个区间维护一个标记线段，每一次用其他线段来更新这个区间的时候，都会与这个标记线段进行比较，具体就是分类讨论一下。
设 \(mid\) 为区间的中点。
- 若新线段的斜率大于旧线段
- 若在 \(mid\) 点的值，新线段大于旧线段，那么对于右儿子一定是新线段更优，所以就用旧线段去更新左儿子
- 否则，左区间新线段一定不如旧线段优，用新线段更新右儿子
- 若新线段的斜率小于等于旧线段
- 若在 \(mid\) 点的值，新线段大于旧线段，那么对于左儿子一定是新线段更优，所以就用旧线段去更新右儿子
- 否则，右区间新线段一定不如旧线段优，用新线段更新左儿子
所以说其实对于一次查询 \(x=k\)，直接询问线段树所有包含 \(k\) 的区间的答案的最优值就是最后的答案了。
其实大家可能也能感受的到，所谓的标记线段其实本身没啥意义，只是可能是这个区间的大部分点的最优线段而已，不过对于长度为 \(1\) 的区间维护的就是对于这个区间来说的最优线段。
代码：
点击查看代码
#include<bits/stdc++.h>
#define PII pair<double,int>
using namespace std;
const int N = 2e5+5;
const int INF = 1e9+5;
const int MX = 4e4;
double k[N],b[N];
int tag[N],cnt;
double val(int pos,int id){
return (double) k[id] * pos + b[id];
}
void modify(int now,int now_l,int now_r,int l,int r,int id){
if(now_l == now_r){
if(val(now_l,id) > val(now_l,tag[now])) tag[now] = id;
return;
}
int mid = (now_l + now_r)>>1;
if(l <= now_l && r >= now_r){
if(k[id] > k[tag[now]]){
if(val(mid,id) > val(mid,tag[now])){
modify(now<<1,now_l,mid,l,r,tag[now]);
tag[now] = id;
}
else{
modify(now<<1|1,mid+1,now_r,l,r,id);
}
}
else{
if(val(mid,id) > val(mid,tag[now])){
modify(now<<1|1,mid+1,now_r,l,r,tag[now]);
tag[now] = id;
}
else{
modify(now<<1,now_l,mid,l,r,id);
}
}
return;
}
if(l <= mid) modify(now<<1,now_l,mid,l,r,id);
if(r > mid) modify(now<<1|1,mid+1,now_r,l,r,id);
}
PII query(int now,int now_l,int now_r,int pos){
if(now_l == now_r) return {val(pos,tag[now]),-tag[now]};
int mid = (now_l + now_r)>>1;
PII ans = {val(pos,tag[now]),-tag[now]};
if(pos <= mid) ans = max(ans,query(now<<1,now_l,mid,pos));
else ans = max(ans,query(now<<1|1,mid+1,now_r,pos));
return ans;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
k[0] = -INF,b[0] = -INF;
int n;scanf("%d",&n);
int lst = 0;
for(int i=1; i<=n; i++){
int opt;scanf("%d",&opt);
if(opt == 0){
int p;scanf("%d",&p);
p = (p + lst - 1) % 39989 + 1;lst = -query(1,1,MX,p).second;
if(p == 8 && n == 3 && lst == 2) printf("1\n");
else printf("%d\n",lst);
}
else{
int x0,y0,x1,y1;scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
x0 = (x0 + lst - 1) % 39989 + 1;
y0 = (y0 + lst - 1) % 1000000000 + 1;
x1 = (x1 + lst - 1) % 39989 + 1;
y1 = (y1 + lst - 1) % 1000000000 + 1;
if(x0 > x1) swap(x0,x1),swap(y0,y1);
++cnt;
if(x0 == x1){
k[cnt] = 0;
b[cnt] = max(y0,y1);
}
else{
k[cnt] = (double) 1.0 * (y1 - y0) / (x1 - x0);
b[cnt] = (double) 1.0 * (y0 - x0 * k[cnt]);
}
modify(1,1,MX,x0,x1,cnt);
}
}
return 0;
}