Blue Mary开公司

题面：[JSOI2008]Blue Mary开公司

题目大意：

每次加入一条形如 \(y=Px + S - P\) 的直线，询问 \(x=T\) 时此处最高的 \(y\) 值（\(S,P,T\)均为题中给出）

思路

很经典的李超树模板，每次在整个线段树中加入一条直线

注意:每天最小收益至少为 \(0\)！！

即你的答案必然不小于 \(0\) ！！

不会李超树的戳这里：李超树学习笔记

\(Code\)

#include<cstdio>

#include<cmath>

using namespace std;

const int T = 50010;

int n , fl[4 * T];

struct tree{

	double k , b;

}seg[4 * T];

inline double max(double x , double y){return x < y ? y : x;}

inline double Intersection(double k1 , double b1 , double k2 , double b2){return 1.0 * (b2 - b1) / (k1 - k2);}

inline void update(double k , double b , int l , int r , int rt)

{

	if (!fl[rt])

	{

		seg[rt].k = k , seg[rt].b = b , fl[rt] = 1;

		return;

	}

	double f1 = seg[rt].k * l + seg[rt].b , f2 = seg[rt].k * r + seg[rt].b;

	double f3 = k * l + b , f4 = k * r + b;

	if (f1 >= f3 && f2 >= f4) return;

	else if (f1 <= f3 && f2 <= f4) seg[rt].k = k , seg[rt].b = b;

	else{

		int mid = (l + r) >> 1;

		double len = Intersection(k , b , seg[rt].k , seg[rt].b);

		if (f1 <= f3)

		{

			if (len <= mid) update(k , b , l , mid , rt << 1);

			else update(seg[rt].k , seg[rt].b , mid + 1 , r , rt << 1 | 1) , seg[rt].k = k , seg[rt].b = b;

		}

		else {

			if (len > mid) update(k , b , mid + 1 , r , rt << 1 | 1);

			else update(seg[rt].k , seg[rt].b , l , mid , rt << 1) , seg[rt].k = k , seg[rt].b = b;

		}

	}

}

inline double query(int l , int r , int rt , int x)

{

	double ans = 1.0 * seg[rt].k * x + seg[rt].b;

	if (l == r) return ans;

	int mid = (l + r) >> 1;

	if (x <= mid) ans = max(ans , query(l , mid , rt << 1 , x));

	else ans = max(ans , query(mid + 1 , r , rt << 1 | 1 , x));

	return ans;

}

int main()

{

	char s[10];

	double b , k;

	int x;

	scanf("%d" , &n);

	for(register int i = 1; i <= 4 * 50005 + 1; i++) seg[i].b = -1e18 , seg[i].k = 0;

	while(n--)

	{

		scanf("%s" , s + 1);

		if (s[1] == 'P')

		{

			scanf("%lf %lf" , &b , &k);

			b = b - k;

			update(k , b , 1 , 5e4 + 5 , 1);

		}

		else {

			scanf("%d" , &x);

			double ans = query(1 , 5e4 + 5 , 1 , x);

			if (ans <= 0) printf("0\n");

			else printf("%d\n" , (int)(ans / 100));

		}

	}

}

巴特西

Blue Mary开公司

Blue Mary开公司

题目大意：

思路

\(Code\)

最新文章

热门文章