建立线段树,每个节点维护该区间内的最优线段。
插入线段时,在线段树上分裂成$O(\log n)$棵子树,若与当前点的最优线段不相交,那么取较优的,否则暴力递归子树。
查询时在叶子到根路径上所有点的最优线段中取个最优的即可。
时间复杂度$O(n\log^2n)$。
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 39989
using namespace std;
struct Seg{
double k,b;
Seg(){}
Seg(int x0,int y0,int x1,int y1){if(x0==x1)k=0,b=max(y0,y1);else k=1.0*(y0-y1)/(x0-x1),b=-k*x0+y0;}
double gety(int x){return k*x+b;}
}s[100010];
int m,op,cnt,X0,Y0,X1,Y1,ans,v[131000];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline int sig(double x){return fabs(x)<1e-8?0:(x>0?1:-1);}
void ins(int x,int a,int b,int c,int d,int p){
if(c<=a&&b<=d){
if(sig(s[p].gety(a)-s[v[x]].gety(a))>0&&sig(s[p].gety(b)-s[v[x]].gety(b))>0){v[x]=p;return;}
if(sig(s[p].gety(a)-s[v[x]].gety(a))<=0&&sig(s[p].gety(b)-s[v[x]].gety(b))<=0)return;
if(a==b)return;
}
int mid=(a+b)>>1;
if(c<=mid)ins(x<<1,a,mid,c,d,p);
if(d>mid)ins(x<<1|1,mid+1,b,c,d,p);
}
void ask(int x,int a,int b,int c){
if(sig(s[ans].gety(c)-s[v[x]].gety(c))<0)ans=v[x];
else if(!sig(s[ans].gety(c)-s[v[x]].gety(c))&&ans>v[x])ans=v[x];
if(a==b)return;
int mid=(a+b)>>1;
c<=mid?ask(x<<1,a,mid,c):ask(x<<1|1,mid+1,b,c);
}
int main(){
s[0].b=-1;
read(m);
while(m--){
read(op);
if(!op){
read(X0),X0=(X0+ans-1)%39989+1;
ans=0,ask(1,1,N,X0);
printf("%d\n",ans);
}else{
read(X0),read(Y0),read(X1),read(Y1);
X0=(X0+ans-1)%39989+1,Y0=(Y0+ans-1)%1000000000+1;
X1=(X1+ans-1)%39989+1,Y1=(Y1+ans-1)%1000000000+1;
s[++cnt]=Seg(X0,Y0,X1,Y1);
if(X0>X1)swap(X0,X1);
ins(1,1,N,X0,X1,cnt);
}
}
return 0;
}
BZOJ3165 : [Heoi2013]Segment的更多相关文章
-
BZOJ3165[Heoi2013]Segment——李超线段树
题目描述 要求在平面直角坐标系下维护两个操作: 1.在平面上加入一条线段.记第i条被插入的线段的标号为i. 2.给定一个数k,询问与直线 x = k相交的线段中,交点最靠上的线段的编号. 输入 第一行 ...
-
2019.02.11 bzoj3165: [Heoi2013]Segment(线段树)
传送门 题意简述:要求支持两种操作: 插入一条线段. 询问与直线x=kx=kx=k相交的线段中,交点最靠上的线段的编号. 思路: 直接上李超线段树即可. 代码: #include<bits/st ...
-
BZOJ3165: [Heoi2013]Segment(李超线段树)
题意 题目链接 Sol 李超线段树板子题.具体原理就不讲了. 一开始自己yy着写差点写自闭都快把叉积搬出来了... 后来看了下litble的写法才发现原来可以写的这么清晰简洁Orz #include& ...
-
【BZOJ3165】[HEOI2013]Segment(李超线段树)
[BZOJ3165][HEOI2013]Segment(李超线段树) 题面 BZOJ 洛谷 题解 似乎还是模板题QwQ #include<iostream> #include<cst ...
-
【BZOJ-3165】Segment 李超线段树(标记永久化)
3165: [Heoi2013]Segment Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 368 Solved: 148[Submit][Sta ...
-
bzoj 3165: [Heoi2013]Segment 动态凸壳
3165: [Heoi2013]Segment Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 202 Solved: 89[Submit][Stat ...
-
洛谷 P4097 [HEOI2013]Segment 解题报告
P4097 [HEOI2013]Segment 题目描述 要求在平面直角坐标系下维护两个操作: 在平面上加入一条线段.记第 \(i\) 条被插入的线段的标号为 \(i\) 给定一个数 \(k\),询问 ...
-
BZOJ 3165: [Heoi2013]Segment
3165: [Heoi2013]Segment Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 465 Solved: 187[Submit][Sta ...
-
Bzoj 3165 [Heoi2013]Segment题解
3165: [Heoi2013]Segment Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 668 Solved: 276[Submit][Sta ...
随机推荐
-
在Main方法中设置异常的最后一次捕捉
在做Winfrom程序时,有时会遇到一个异常,可是这个异常不知道在什么地方发生的,程序会自动关闭,然后什么也没有了,在网上找到了一种方法,用来捕捉这种异常. 出现这种情况的原因是在程序中某些地方考虑不 ...
-
php图片验证码为什么必须加上ob_clean();才能正常显示。
ob_clean这个函数的作用就是用来丢弃输出缓冲区中的内容,如果你的网站有许多生成的图片类文件,那么想要访问正确,就要经常清除缓冲区. If you work on an extremely lar ...
-
嵌入式linux应用开发完全手册学习笔记一
2015.3.25星期三 晴 有两个星期没写学习日记了,找个时间把这段时间做的电子词典和ARM小项目总结一下. 下面的知识点总结,U-BOOT:参考PDF文档:嵌入式linux应用开发完全手册 当虚拟 ...
-
xshell 5连接linux服务器的技巧
1.用sttp 方式连接服务器,命令识别不了,用ssh方式才能有效
-
OpenCV 读取.xml文件
OpenCV 只提供了读取和存储.xml和.yml 文件格式的函数. 读取.xml文件的C++例程如下: cv::FileStorage fs; //OpenCV 读XML文件流 cv::Mat De ...
-
安装qc 出现error An error occurred while attempting to connect to the database.
When trying to install mercury quality center starter edition 9.0 on Windows XP media center, I am g ...
-
【剑指Offer学习】【面试题43 : n 个锻子的点数】
题目:把n个骰子扔在地上,全部骰子朝上一面的点数之和为s.输入n.打印出s 的全部可能的值出现的概率. 解题思路 解法一:基于通归求解,时间效率不够高. 先把n个骰子分为两堆:第一堆仅仅有一个.还有一 ...
-
Monkey学习笔记<;四>;:Monkey服务器命令
#使用如下命令将本地pc和手机连接起来 adb shell monkey --port 1080 adb forward tcp 1080:tcp 1080 telnet localhost 1080 ...
-
ie8下的透明 问题
团队里经常遇到,索性整理一起 是我们在前端开发中经常遇到的,在问题中经常遇到的两个问题是背景色透明和整体透明 先说下背景色透明,背景色透明,在现代浏览器中,可以用rgba颜色作为背景色. 简单介绍下r ...
-
ORACLE中CHAR、VARCHAR、NVARCHAR
1. char 固定长度,最长n个字符. 2. varchar 最大长度为n的可变字符串. (n为某一整数,不同数据库,最大长度n不同) char和varchar区别: ...