自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 22:11:56，当前版本为作者最后更新于2019-09-12 16:46:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人： hsfzLZH1

本题主要考察模型转化和线段树。

题目大意

$m$ 次操作，每次操作为以下两种之一：

1. add a v l r ，告诉你有一个篮球，在时间段 $[l,r]$ 时在空中，时刻 $l$ 时的高度为 $a$ ，初始向上速度为 $v$ 。篮球的高度 $h$ 随在空中的时长 $t$ 的变化为 $h=-\dfrac 1 2 gt^2+vt+a$ 。

2. query x ，询问在时刻 $x$ ，所有已知的在空中的篮球中，最高的一个的高度是多少。 如果此时不存在在空中的篮球，输出 Undefined 。

30pts

记录已知的所有篮球的 $a,v,l,r$ ，对一个时刻进行查询时，判断每个球是否在空中，如果是，计算这个球此时的高度，并取最大值即可。时间复杂度 $O(m^2)$ 。

60pts

将时间轴当做横坐标，篮球的高度当做纵坐标。

篮球的高度 $h$ 与时刻 $x$ 的关系式： $h=-\dfrac 1 2 g(x-l)^2+v(x-l)+a$

$h=-\dfrac 1 2 gx^2+(v+gl)x-\dfrac 1 2 gl^2-vl+a$

每次询问，给定 $x$ ，而 $a,v,l,r$ 的取值会随着线段的不同而不同，此时 $-\dfrac 1 2 gx^2$ 为定值。对每个篮球，令 $k=v+gl,b=-\dfrac 1 2 gl^2-vl+a$ ，你需要求出满足 $l\le x\le r$ 时最大的 $kx+b$ 。

由此，问题转化为两种操作：

1. 在平面上插入一条线段。

2. 求所有与 $x=c$ 相交的线段中交点 $y$ 坐标最大的一个。

这就是 李超线段树 的模板题了。由于题目中有小数，可以将所有时间乘以 $1000$ 后转化为整数。令 $n=1000\times x$ ，时间复杂度 $O(n\log_2^2 n)$ ，空间复杂度 $O(n)$ 。

100pts

注意到 $n$ 的值可能很大，此时可以用 询问离线+离散化 或 动态开点 的方法减小 $n$ 的值。

参考代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define double long double
using namespace std;
const int maxn=100010;
const int inf=1e9+1;
const int ddd=20000010;
const double g=9.8;
int m,cur;
char op[10];
double a,v,x,l,r;
struct seg
{
	double a,b;
	double f(double x){return x*a+b;}
}s[maxn];
int rt,cnt,lc[ddd],rc[ddd],id[ddd];
void update(int&o,int l,int r,int ql,int qr,int v)
{
	if(r<ql||l>qr)return;
	if(!o)o=++cnt;
	if(ql<=l&&r<=qr)
	{
		if(!id[o])id[o]=v;
		else
		{
			if(s[v].f(l/1000.0)>=s[id[o]].f(l/1000.0)&&s[v].f(r/1000.0)>=s[id[o]].f(r/1000.0)){id[o]=v;return;}
			if(s[v].f(l/1000.0)<=s[id[o]].f(l/1000.0)&&s[v].f(r/1000.0)<=s[id[o]].f(r/1000.0))return;
			if(l==r)return; 
			int mid=(l+r)>>1;
			if(s[v].f(l/1000.0)>=s[id[o]].f(l/1000.0))
			{
				if(s[v].f(mid/1000.0)>=s[id[o]].f(mid/1000.0))update(rc[o],mid+1,r,ql,qr,id[o]),id[o]=v;
				else update(lc[o],l,mid,ql,qr,v);
			}
			else
			{
				if(s[v].f(mid/1000.0)<=s[id[o]].f(mid/1000.0))update(rc[o],mid+1,r,ql,qr,v);
				else update(lc[o],l,mid,ql,qr,id[o]),id[o]=v;
			}
		}
		return;
	}
	int mid=(l+r)>>1;
	update(lc[o],l,mid,ql,qr,v);
	update(rc[o],mid+1,r,ql,qr,v);
}
int query(int o,int l,int r,int x)
{
	if(!o)return 0;
	if(l==r)return id[o];
	int mid=(l+r)>>1,ans;
	if(x<=mid)ans=query(lc[o],l,mid,x);
	else ans=query(rc[o],mid+1,r,x);
	if(!id[o])return ans;
	if(!ans)return id[o];
	if(s[id[o]].f(x/1000.0)>=s[ans].f(x/1000.0))return id[o];
	return ans;
}
main()
{
	scanf("%d",&m);
	while(m--)
	{
		scanf("%s",op);
		if(op[0]=='a')
		{
			cur++;
			scanf("%Lf%Lf%Lf%Lf",&a,&v,&l,&r);
			s[cur].a=v+g*l;s[cur].b=a-g/2*l*l-v*l;
			update(rt,-inf,inf,(int)(l*1000.0),(int)(r*1000.0),cur);
		}
		else
		{
			scanf("%Lf",&x);
			int t=query(rt,-inf,inf,(int)(x*1000.0));
			if(!t)printf("Undefined\n");
			else printf("%Lf\n",-g/2*x*x+s[t].a*x+s[t].b);
		}
	}
	return 0;
}