BZOJ 1568: [JSOI2008]Blue Mary開公司(超哥線段樹)

Description

Input

Output

Sample Input

Sample Output

HINT

Source

超哥線段樹的模板題。

超哥線段樹是處理一次函數的一種線段樹，

在超哥線段樹中，每一個節點保存著一個一次函數所對應的編號，

那他是怎麼保存的呢？

借用一位大神的圖片

沒錯就是這樣，

然後對於每一次插入操作，

我們去遞歸當前 值小的節點 的值 可能比 值大的節點 的 值 大的方向。。。。。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int MAXN=1000001;
inline void read(int &n)
{
	char c='+';int x=0;bool flag=0;
	while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
	while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
	n=flag==1?-x:x;
}
struct funtion
{
	double k,b;
}a[MAXN];// 記錄每一條線段 
int tree[MAXN];// 每一個節點所對應線段的編號 
int tot=0;// 總的線段數量 
inline int pd(int now,int will,int day)
{
	--day;
	return a[now].k*day+a[now].b>a[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<=mid)	query(ls,l,mid,now);
	else 	query(rs,mid+1,r,now);
}
int main()
{
	ios::sync_with_stdio(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string opt;
		cin>>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;
}