当前位置: 首页 > news >正文

李超线段树

李超线段树

image

// 李超线段树 O(nlognlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const double eps=1e-9;
const int N=100005;
#define M1 39989
#define M2 1000000000
#define ls u<<1
#define rs u<<1|1
typedef pair<double,int> pdi;
int n,cnt,lastans;
struct line{double k,b; //斜率,截距
}p[N];        
int tr[N<<2]; //线段编号int cmp(double a,double b){ //比a,bif(a-b>eps) return 1;if(b-a>eps) return -1;return 0;
}
double Y(int id,int x){ //求Y值return p[id].k*x+p[id].b;
}
void change(int u,int l,int r,int L,int R,int id){ //修改int mid=(l+r)>>1;if(L<=l&&r<=R){int cm=cmp(Y(id,mid),Y(tr[u],mid));if(cm==1||(!cm&&id<tr[u])) swap(id,tr[u]);int cl=cmp(Y(id,l),Y(tr[u],l));if(cl==1||(!cl&&id<tr[u])) change(ls,l,mid,L,R,id);int cr=cmp(Y(id,r),Y(tr[u],r));if(cr==1||(!cr&&id<tr[u])) change(rs,mid+1,r,L,R,id);return;}if(L<=mid) change(ls,l,mid,L,R,id);if(mid<R) change(rs,mid+1,r,L,R,id);
}
pdi pmax(pdi a,pdi b){ //Y值大且编号小if(cmp(a.first,b.first)==1) return a;else if(cmp(a.first,b.first)==-1) return b;else return a.second<b.second ? a : b;
}
pdi query(int u,int l,int r,int x){ //查询if(l==r) return {Y(tr[u],x),tr[u]};int mid=(l+r)>>1;pdi t={Y(tr[u],x),tr[u]};if(x<=mid) return pmax(t,query(ls,l,mid,x));else return pmax(t,query(rs,mid+1,r,x));
}
int main(){int op,x0,y0,x1,y1,x; double k,b;scanf("%d",&n);while(n--){scanf("%d",&op);if(op==1){scanf("%d%d%d%d",&x0,&y0,&x1,&y1);x0=(x0+lastans-1)%M1+1,x1=(x1+lastans-1)%M1+1;y0=(y0+lastans-1)%M2+1,y1=(y1+lastans-1)%M2+1;if(x0>x1) swap(x0,x1),swap(y0,y1);if(x0==x1) k=0,b=max(y0,y1);else k=1.0*(y1-y0)/(x1-x0),b=y0-k*x0;   p[++cnt]={k,b};change(1,1,M1,x0,x1,cnt);}else{scanf("%d",&x);x=(x+lastans-1)%M1+1;lastans=query(1,1,M1,x).second;printf("%d\n",lastans);}}
}
http://www.hskmm.com/?act=detail&tid=36822

相关文章:

  • fiddler修改请求(修改搜索框的内容)
  • 20251022
  • 10月22号
  • 将“百度”的URL改为“163网易云”(修改URL地址)
  • Yolo11分割模型
  • 星旗笔试
  • 智联笔记项目——251022登录注册、后端管理及内容类型处理优化
  • 2025.10.22博客
  • 这是一个测试文档
  • JavaScript formatter插件的使用
  • 完整教程:基于WebAssembly的STEP文件3D在线查看器实现详解
  • 20232407 2025-2026-1 《网络与系统攻防技术》 实验二实验报告
  • 10.21 CSP-S模拟36 改题记录
  • 20232406 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 程序员必备!5款小白也能秒上手的AI编程工具
  • 笔记本 copilot按键 PowerToys映射
  • 实用指南:86-python电网可视化项目-6
  • 详细介绍:3.5mm耳机插座技术全解析:从镀层工艺到阻抗稳定性测试
  • 通过电脑调试 Android/iOS 手机端网页
  • CMS垃圾回收器详解
  • 网页自动转发替换图片
  • JavaScript 自定义元素类的作用域跨环境兼容管理
  • JMeter使用
  • 解决 Semi Design Upload 组件实现自定义压缩,上传文件后无法触发 onChange
  • QT实现QTreeWidget项目拖拽移动功能
  • lora学习笔记
  • 自动化释放5G全部潜力:新西兰电信One NZ的实践之路
  • cookie机制如何获取用户个人信息
  • 数据库——聚合函数
  • 第二十一篇