2018.07.23 洛谷P4097 [HEOI2013]Segment(李超线段树)
2024-08-25 21:03:04
传送门
给出一个二维平面,给出若干根线段,求出x" role="presentation" style="position: relative;">xx坐标为x0" role="presentation" style="position: relative;">x0x0时在最上方的线段的标号(若有多条输出最小的)。
线段树好题,这题是李超线段树板子题。
没学过的这道题可以让你很好的理解李超线段树,下面讲讲这是什么东西。
先闲扯一句没用的:维护这个信息就相当于维护实数域上插入等差数列求单点的最大值的最小标号。
下面切入正题:
李超线段树的每个节点Tl,r" role="presentation" style="position: relative;">Tl,rTl,r维护的是这个区间内的的最优线段,其实就是指覆盖此区间且暴露最多的线段。
注意:也就是说父亲和儿子维护的线段的标号可能不同。
比如说这个图(图有点丑请别介意)。
对于整个区间应该是红线最优,对于左儿子那个区间应该是绿线更优,对于右儿子那个区间应该是蓝线最优。
不难看出一个区间最优线段的选取是与交点的位置,mid" role="presentation" style="position: relative;">midmid,和两条直线的最左边的上下关系有关的。
具体实现:
修改:
如果当前区间没有插入:直接修改。
如果当前区间比插入的直线优:不管了
如果当前区间没有插入的直线优:直接修改。
查询:
可以看出对于一个横坐标的最优值只与所有覆盖了这个横坐标的最优线段的最优值有关,因此可以递归查询。
代码如下:
#include<bits/stdc++.h>
#define N 100005
#define modx 39989
#define mody 1000000000
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void write(int x){
if(x>9)write(x/10);
putchar((x%10)^48);
}
struct line{int l,r,id;double k,b;}q[N];
struct node{int l,r,id;}T[N<<2];
int n,cnt=0;
inline bool check(int idx,int idy,int pos){
if(!idx)return true;
double h1=pos*q[idx].k+q[idx].b,h2=pos*q[idy].k+q[idy].b;
return h1==h2?idx<idy:h1<h2;
}
inline int query(int p,int k){
if(T[p].l==T[p].r)return T[p].id;
int mid=T[p].l+T[p].r>>1,tmp;
if(k<=mid)tmp=query(lc,k);
else tmp=query(rc,k);
return check(T[p].id,tmp,k)?tmp:T[p].id;
}
inline void change(int p,int k){
if(!T[p].id)T[p].id=k;
if(check(T[p].id,k,T[p].l))swap(k,T[p].id);
if(T[p].l==T[p].r||q[T[p].id].k==q[k].k)return;
int mid=T[p].l+T[p].r>>1;
double tmpx=(q[T[p].id].b-q[k].b)/(q[k].k-q[T[p].id].k);
if(tmpx<T[p].l||tmpx>T[p].r)return;
if(tmpx<=mid)change(lc,T[p].id),T[p].id=k;
else change(rc,k);
}
inline void update(int p,int k){
if(q[k].l<=T[p].l&&T[p].r<=q[k].r){change(p,k);return;}
int mid=T[p].l+T[p].r>>1;
if(q[k].l<=mid)update(lc,k);
if(q[k].r>mid)update(rc,k);
}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r)return;
int mid=T[p].l+T[p].r>>1;
build(lc,l,mid),build(rc,mid+1,r);
}
int main(){
build(1,1,50000);
n=read();
int x1,x2,y1,y2,op,lastans=0;
while(n--){
op=read();
switch(op){
case 0:{
x1=(read()+lastans-1)%modx+1;
cout<<(lastans=query(1,x1))<<'\n';
break;
}
default:{
++cnt;
x1=(read()+lastans-1)%modx+1;
y1=(read()+lastans-1)%mody+1;
x2=(read()+lastans-1)%modx+1;
y2=(read()+lastans-1)%mody+1;
if(x1>x2)x1^=x2,x2^=x1,x1^=x2,y1^=y2,y2^=y1,y1^=y2;
if(x1==x2)q[cnt].k=0,q[cnt].b=max((double)y1,(double)(y2));
else q[cnt].k=(double)(y1-y2)/(x1-x2),q[cnt].b=(double)y1-q[cnt].k*x1;
q[cnt].l=x1,q[cnt].r=x2,q[cnt].id=cnt;
update(1,cnt);
break;
}
}
}
return 0;
}
最新文章
- [No000099]软件版本命名规范
- jquery基本操作笔记
- django之DB操作
- MySQL主主复制
- Android高手速成
- 使用 Intel HAXM 为 Android 模拟器加速,媲美真机
- React入门2
- 含有GROUP BY子句的查询中如何显示COUNT()为0的成果(分享)
- (转) [老老实实学WCF] 第三篇 在IIS中寄存服务
- Double Strings Solved Problem code: DOUBLE
- Github 常用命令
- Azure Traffic Manager 现可与 Azure 网站集成!
- Zookeeper 笔记-watch
- laravel5.4 后台RBAC功能完成中遇到的问题及解决方法
- maven web工程 解决了pom.xml报错之后,maven web工程还是有个红色的叉叉 解决
- ipython 编辑器 jupyter notebook如何将 ipynb 转成 py 并在 jupyter notebook 中继续引用
- baby用品
- TryParse用法
- 【转】关于Vue打包的一个要注意的地方
- 【实用工具】google访问不了比较好的解决办法