李超线段树 - JSOI2008BlueMary开公司

2021-04-02 01:26

阅读：397

标签：模板题维护 long cout 动态插入技术 mod 交点 odi

李超线段树用来在平面内动态插入线段，求\(x=t\)直线与这些线段交点的最值

核心是维护每个区间的“最优势线段”，即终点位置处最高的线段，询问室对所有包含\(t\)的区间的最优势线段计算答案，最后取\(max\)

技术图片

模板题：JSOI2008BlueMary开公司

插入直线，求单点最大值

（看代码）

#include
using namespace std;
const int N=50004;
#define lc (p>1;
	double l1=l*k+b,r1=r*k+b;
	double l2=l*tk[p]+tb[p],r2=r*tk[p]+tb[p];
	if(l1l2&&r1>r2){tk[p]=k;tb[p]=b;return;}
	double x=(b-tb[p])/(tk[p]-k);
	if(l1>l2){
		if(x>mid){
			modify(rc,mid+1,r,tk[p],tb[p]);
			tk[p]=k;tb[p]=b;
		}
		else modify(lc,l,mid,k,b);
	}
	else{
		if(x>mid)modify(rc,mid+1,r,k,b);
		else{
			modify(lc,l,mid,tk[p],tb[p]);
			tk[p]=k;tb[p]=b;
		}
	}
}
double query(int p,int l,int r,int x){
	if(l==r)return tk[p]*x+tb[p];
	int mid=l+r>>1;
	double ret=tk[p]*x+tb[p];
	if(x

李超线段树 - JSOI2008BlueMary开公司

标签：模板题维护 long cout 动态插入技术 mod 交点 odi

原文地址：https://www.cnblogs.com/aurora2004/p/12558122.html

上一篇：webrtc测试小工具

下一篇：407 ES6的模块语法 (基于webpack)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：李超线段树 - JSOI2008BlueMary开公司
文章链接：http://soscw.com/index.php/essay/71179.html

亲，登录后才可以留言！

李超线段树 - JSOI2008BlueMary开公司

评论

热门文章

推荐文章

最新文章

置顶文章