题解 P5554 【篮球统计】

· · 题解

出题人： hsfzLZH1

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

题目大意

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;
}