文档章节

[JSOI2008]Blue Mary开公司

o
 osc_vh2swrce
发布于 2018/02/04 22:01
字数 1285
阅读 23
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

Description!

Input 第一行 :一个整数N ,表示方案和询问的总数。 接下来N行,每行开头一个单词“Query”或“Project”。 若单词为Query,则后接一个整数T,表示Blue Mary询问第T天的最大收益。 若单词为Project,则后接两个实数S,P,表示该种设计方案第一天的收益S,以及以后每天比上一天多出的收益P。 1 <= N <= 100000 1 <= T <=50000 0 < P < 100,| S | <= 10^6 提示:本题读写数据量可能相当巨大,请选手注意选择高效的文件读写方式。

Output 对于每一个Query,输出一个整数,表示询问的答案,并精确到整百元(以百元为单位,例如:该天最大收益为210或290时,均应该输出2)。 没有方案时回答询问要输出0

Sample Input 10 Project 5.10200 0.65000 Project 2.76200 1.43000 Query 4 Query 2 Project 3.80200 1.17000 Query 2 Query 3 Query 1 Project 4.58200 0.91000 Project 5.36200 0.39000

Sample Output 0 0 0 0 0


写这个题目,我们需要用到线段树的标记永久化。那么什么是线段树的标记永久化呢? 所谓标记永久化,是指线段树的标记不会下传,那么我每次询问的时候把叶子到根的路径上的信息处理下就好了。 不会下传的标记?那有什么用? 用处其实非常多,例如常数小,或者说有些题目在标记下传的时候无法维护信息,这样可以用标记永久化。

那么这题呢?的确是标记永久化,不过不绝对。 首先本题的方案都可以看做是一条直线,那么这题便转化成了插入n条直线,然后询问某x位置的最大的y。

每次加入一条直线时,首先判断该直线与区间所记录的直线(记录在Mid)的斜率大小,然后判断在Mid点时,哪条直线的答案更优

如果是斜率大的答案更优,那么在(Mid,r]内,一定是斜率大的答案优,因此我们只需要将斜率小的直线下放到左儿子,并且将当前区间记录的直线更新为斜率大的直线;如果是斜率小的答案更优,那么在[l,Mid]内一定是斜率小的更优,所以我们就将斜率大的直线传到右儿子中递归更新,当前区间同样更新

其实读到这里应该还会有个小问题,由于线段树上记录的是一段段的折线,并且这些折线斜率必定递增。我们在上文所说的某条直线在更新了区间记录的答案后,就把另一条直线往一边下放了,难道另一边不用下放吗?又或者说,当前记录的新直线,不用在另一边下放,判断一下,更新一下吗?

标记永久化带来的这个疑问,必然有解决的方法。我们统计答案的时候,将路过的所有直线都计算一下,更新答案,就不会有什么问题了。

又或者我们换个思想,每个区间所记录的直线,只是保证Mid最优的直线,那么我们的问题也就解决了

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
	int x=0,f=1;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')    f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
inline void print(int x){
	if (x>=10)     print(x/10);
	putchar(x%10+'0');
}
const int N=1e5,Day=5e4;
double K[N+10],B[N+10];  //K是斜率,B是与y轴交点(来自初中数学的摧残)
int Lazy[N*4+10];  //标记记录的不是斜率,是序号
char s[10];
#define ls (p<<1)
#define rs (p<<1|1)
bool check(int x,int y,int cnt){return K[x]*(cnt-1)+B[x]>K[y]*(cnt-1)+B[y];}//位于cnt点的两直线判断
void change(int p,int l,int r,int t){
	if (l==r){
		if (check(t,Lazy[p],l))	Lazy[p]=t;
		return;
	}
	int mid=(l+r)>>1;
	if (K[t]>K[Lazy[p]]){//将判断对照前面的文字说明便十分明了
		if (check(t,Lazy[p],mid))	change(ls,l,mid,Lazy[p]),Lazy[p]=t;
		else	change(rs,mid+1,r,t);
	}
	if (K[t]<K[Lazy[p]]){
		if (check(t,Lazy[p],mid))	change(rs,mid+1,r,Lazy[p]),Lazy[p]=t;
		else	change(ls,l,mid,t);
	}
}
double get(int x,int cnt){return K[x]*(cnt-1)+B[x];}//得到cnt点的答案
double query(int p,int l,int r,int t){
	if (l==r)	return get(Lazy[p],t);
	int mid=(l+r)>>1;
	double ans=get(Lazy[p],t);  //一路更新答案
	if (t<=mid)	ans=max(ans,query(ls,l,mid,t));
	if (t>mid)	ans=max(ans,query(rs,mid+1,r,t));
	return ans;
}
int main(){
	int n=read(),cnt=0;
	for (int i=1;i<=n;i++){
		scanf("%s",s+1);
		if (s[1]=='P'){
			cnt++;
			scanf("%lf%lf",&B[cnt],&K[cnt]);
			change(1,1,Day,cnt);  //题目并未告诉你明确的天数,因此只能这么玩
		}
		if (s[1]=='Q'){
			int x=read();
			double t=query(1,1,Day,x);
			printf("%d\n",(int)t/100);  //按题目要求输出
		}
	}
	return 0;
}
下一篇: HBase 权限控制
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
端口映射程序--PS320

PS320 V0.12 版本为开源版本 本程序最初想解决自己管理服务器问题,当初因客户不对外开放端口,导致管理工作量大,速度慢且不稳定,每次管理都去现场处理。 本程序提供端口映射功能,可以直接...

冰迪
2013/06/03
2.1K
0
windows socket api 封装库--xgnet

稳定易用的大容量 windows socket api 封装库,采用重叠完成端口模型实现,引擎采用异步消息控制,实现了一个简明易用的网络框架,发送和接收数据全都采用异步模式,发送和接收数据都不会给调...

pilgarlicx
2013/06/04
2.6K
0
为何受伤的总是技术人:《大牛被公司诬蔑,还要进派出所?》前传

《大牛被公司诬蔑,还要进派出所?》前传,为何受伤的总是技术人 事件简介:原 大牛被公司诬蔑,还要进派出所? 争论要点 1)一个巴掌拍不响? 2)程序员是"危险"行业,跟商人无法比,只有被...

i5ting
2016/05/15
7.1K
29
开题报告问题

文字识别 图像预处理 单字切割 文字特征抽取 对比数据库 1,图像预处理 手机屏幕的每一个像素都是由计算机中24位数表示的,每个像素都包含红(R) 绿(G)蓝(B)三种色彩分量,可表示为RGB C X, ...

761218914
2016/01/18
1
0
Python 中的枚举类型

枚举类型可以看作是一种标签或是一系列常量的集合,通常用于表示某些特定的有限集合,例如星期、月份、状态等。Python 的原生类型(Built-in types)里并没有专门的枚举类型,但是我们可以通...

rainyear
2016/04/30
2.3K
0

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-08-15

最后更新时间: 2020-08-15 06:01 Welders set off Beirut blast while securing explosives - (maritime-executive.com) 焊工在固定炸药的同时引爆了贝鲁特爆炸 得分:347 | 评论:302 Factor......

FalconChen
今天
24
0
OSChina 周六乱弹 —— 老椅小猫秋乡梦 梦里石台堆小鱼

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @小小编辑 :《MOM》- 蜡笔小心 《MOM》- 蜡笔小心 手机党少年们想听歌,请使劲儿戳(这里) @狄工 :腾讯又在裁员了,35岁以上清退,抖音看到...

小小编辑
今天
111
3
构建高性能队列,你不得不知道的底层知识!

前言 本文收录于专辑:http://dwz.win/HjK,点击解锁更多数据结构与算法的知识。 你好,我是彤哥。 上一节,我们一起学习了如何将递归改写为非递归,其中,用到的数据结构主要是栈。 栈和队列...

彤哥读源码
今天
17
0
Anaconda下安装keras和tensorflow

Anaconda下安装keras和tensorflow 一、下载并安装Anaconda: Anaconda下载 安装步骤: 如果是多用户操作系统选择All Users,单用户选择Just Me 选择合适的安装路径 然后勾选这个,自动配置环境...

Atlantis-Brook
今天
15
0
滴滴ElasticSearch千万级TPS写入性能翻倍技术剖析

桔妹导读:滴滴ElasticSearch平台承接了公司内部所有使用ElasticSearch的业务,包括核心搜索、RDS从库、日志检索、安全数据分析、指标数据分析等等。平台规模达到了3000+节点,5PB 的数据存储...

滴滴技术
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部