文档章节

【BZOJ3165】[HEOI2013]Segment(李超线段树)

o
 osc_n6euf5h6
发布于 2019/03/19 20:05
字数 516
阅读 9
收藏 0

精选30+云产品,助力企业轻松上云!>>>

【BZOJ3165】[HEOI2013]Segment(李超线段树)

题面

BZOJ 洛谷

题解

似乎还是模板题QwQ

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define MAX 100100
#define lson (now<<1)
#define rson (now<<1|1)
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int N=100000;
struct Node
{
	bool fl;int id;double k,b;
	void upd(int _id,double _k,double _b){id=_id,k=_k;b=_b;}
}t[MAX<<2];
double K[MAX],B[MAX];
void Modify(int now,int l,int r,int id,double k,double b)
{
	if(!t[now].fl){t[now].fl=true;t[now].upd(id,k,b);return;}
	int mid=(l+r)>>1;
	double l1=l*t[now].k+t[now].b,r1=r*t[now].k+t[now].b;
	double l2=l*k+b,r2=r*k+b;
	if(l1>=l2&&r1>=r2)return;
	if(l2>l1&&r2>r1){t[now].upd(id,k,b);return;}
	double x=(t[now].b-b)/(k-t[now].k);
	if(x<=mid)
	{
		if(l1>l2)Modify(lson,l,mid,t[now].id,t[now].k,t[now].b),t[now].upd(id,k,b);
		else Modify(lson,l,mid,id,k,b);
	}
	else
	{
		if(l1>l2)Modify(rson,mid+1,r,id,k,b);
		else Modify(rson,mid+1,r,t[now].id,t[now].k,t[now].b),t[now].upd(id,k,b);
	}
}
void Modify(int now,int l,int r,int L,int R,int id,double k,double b)
{
	if(L<=l&&r<=R){Modify(now,l,r,id,k,b);return;}
	int mid=(l+r)>>1;
	if(L<=mid)Modify(lson,l,mid,L,R,id,k,b);
	if(R>mid)Modify(rson,mid+1,r,L,R,id,k,b);
}
void Cmax(int &a,int b,int x)
{
	double ya=K[a]*x+B[a];
	double yb=K[b]*x+B[b];
	if(ya<yb||(fabs(ya-yb)<1e-7&&a>b))a=b;
}
int Query(int now,int l,int r,int x)
{
	if(l==r)return t[now].id;
	int mid=(l+r)>>1,ret=t[now].id;
	if(x<=mid)Cmax(ret,Query(lson,l,mid,x),x);
	else Cmax(ret,Query(rson,mid+1,r,x),x);
	return ret;
}
int Q,ans,tot;
int main()
{
	Q=read();
	while(Q--)
	{
		int opt=read();
		if(!opt)
		{
			int x=((read()+ans-1)%39989+1);
			ans=Query(1,1,N,x);
			printf("%d\n",ans);
		}
		else
		{
			int x0=(read()+ans-1)%39989+1,y0=(read()+ans-1)%1000000000+1;
			int x1=(read()+ans-1)%39989+1,y1=(read()+ans-1)%1000000000+1;
			if(x0>x1)swap(x0,x1),swap(y0,y1);
			++tot;K[tot]=1.0*(y0-y1)/(x0-x1);B[tot]=y0-K[tot]*x0;
			Modify(1,1,N,x0,x1,tot,K[tot],B[tot]);
		}
	}
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Java线程池

前言 Java中对线程池的抽象是ThreadPoolExecutor类,Executors是一个工具类,内置了多种创建线程池的方法: newFixedThreadPool:固定长度线程池 newCachedThreadPool :可缓存线程池 newSin...

nullpointerxyz
11分钟前
29
0
Python笔记:用Python制作二维码

这些年,二维码在我国的日常使用频率特别大。因为其具有简单及安全性吧!除了用网络工具制作二维码,其实用JavaScript或Python也可以制作二维码,而且更有个性。 示例一(制作普通黑白二维码...

tengyulong
23分钟前
0
0
Redis-初体验/数据结构

定义: Redis 是 C 语言开发的一个开源的(遵从 BSD 协议)高性能键值对(key-value)的内存数据库,可以用作数据库、缓存、消息中间件等。它是一种 NoSQL(not-only sql,泛指非关系型数据库...

心田已荒
26分钟前
15
0
如何在保留订单的同时从列表中删除重复项? - How do you remove duplicates from a list whilst preserving order?

问题: Is there a built-in that removes duplicates from list in Python, whilst preserving order? 是否有内置的程序在保留顺序的同时从Python列表中删除重复项? I know that I can us...

fyin1314
今天
29
0
以太坊智能合约开发常见的10个安全问题

本文介绍CheckMarx安全研究小组通过扫描公开的以太坊智能合约所发现的Solidity智能合约开发中常见的十大安全问题,其中__未检查的外部调用__ 和 高成本循环 分列排行榜前两名。该安全问题排行...

区块链教程
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部