BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树)

2021-06-08 22:06

阅读：619

标签：设计 1.4 技术分享 class online 线段接下来目标 ref

1568: [JSOI2008]Blue Mary开公司

Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 1080 Solved: 379
[Submit][Status][Discuss]

Description

技术分享

Input

第一行：一个整数N ，表示方案和询问的总数。

接下来N行，每行开头一个单词“Query”或“Project”。

若单词为Query，则后接一个整数T，表示Blue Mary询问第T天的最大收益。

若单词为Project，则后接两个实数S，P，表示该种设计方案第一天的收益S，以及以后每天比上一天多出的收益P。

提示：本题读写数据量可能相当巨大，请选手注意选择高效的文件读写方式。

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

HINT

Source

超哥线段树的模板题。

超哥线段树是处理一次函数的一种线段树，

在超哥线段树中，每一个节点保存着一个一次函数所对应的编号，

那他是怎么保存的呢？

借用一位大神的图片

技术分享

没错就是这样，

然后对于每一次插入操作，

我们去递归当前值小的节点的值可能比值大的节点的值大的方向。。。。。。。

#include
#include
#include
#include
#include
#define ls k‘9‘){c=getchar();if(c==‘-‘)flag=1;}
	while(c>=‘0‘&&ca[will].k*day+a[will].b;
}
inline void insert(int k,int l,int r,int now)
{
	if(l==r)
	{
		if(pd(now,tree[k],l))	tree[k]=now;
		return ;
	}
	int mid=(l+r)>>1;
	if(a[now].k>a[tree[k]].k)// 当前点的斜率比目标点的斜率大 
	{
		if(pd(now,tree[k],mid))	insert(ls,l,mid,tree[k]),tree[k]=now;
		else	insert(rs,mid+1,r,now);
	}
	else
	{
		if(pd(now,tree[k],mid))	insert(rs,mid+1,r,tree[k]),tree[k]=now;
		else	insert(ls,l,mid,now);
	}
}
double ans=0;
void query(int k,int l,int r,int now)
{
	ans=max(ans,a[tree[k]].k*(now-1)+a[tree[k]].b);
	if(l==r)	return ;
	int mid=(l+r)>>1;
	if(now>n;
	for(int i=1;i>opt;
		if(opt[0]==‘P‘)
		{
			++tot;
			cin>>a[tot].b>>a[tot].k;
			insert(1,1,n,tot);
		}
		else if(opt[0]==‘Q‘)
		{
			int p;
			cin>>p;
			ans=0;
			query(1,1,n,p);
			printf("%d\n",(int)(ans/100));
		}
	}
	return 0;
}

BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树)

标签：设计 1.4 技术分享 class online 线段接下来目标 ref

原文地址：http://www.cnblogs.com/zwfymqz/p/7305682.html

上一篇：js题集5

下一篇：js题集23

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树)
文章链接：http://soscw.com/essay/92406.html

亲，登录后才可以留言！

BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树)

1568: [JSOI2008]Blue Mary开公司

Description

Input

Output

Sample Input

Sample Output

HINT

Source

评论

热门文章

推荐文章

最新文章

置顶文章