[HDU 6759]Leading Robots

Description

题库链接

给出 \(n\) 个二次函数 \(f_i(t)=\frac{1}{2}a_it^2+p_i\)。问函数 \(g(t)=\max\limits_{1\leq i\leq n}\{f_i(t)\},t\in[0,+\infty)\) 是由几个函数组成的。若 \(t_0\) 时刻同时有多个 \(f\) 为最大值，那么 \(g\) 函数上 \(t=t_0\) 不能被考虑。多测，测试组数 \(t\)。

\(1\leq n\leq 50000,1\leq t\leq 50\)

Solution

我的做法有点复杂。

首先可以确定，当 \(a\) 相等时，只需要保留最大的 \(p\) 所对应的二次函数即可。因此可以保证下述讨论中 \(a\)，均不相同。将处理后的函数按 \(a\) 从小到大排序。

对于第 \(i\) 个函数，若它能在某个时刻最大，那么 \[\begin{aligned}\forall j\neq i,\exists t_0,&\frac{1}{2}a_it_0^2+p_i>\frac{1}{2}a_jt_0^2+p_j\\\Rightarrow&\frac{1}{2}t_0^2(a_i-a_j)>p_j-p_i\\\Rightarrow&\left\{\begin{aligned}\frac{1}{2}t_0^2>\frac{p_j-p_i}{a_i-a_j},&i>j\\\frac{1}{2}t_0^2<\frac{p_j-p_i}{a_i-a_j},&i

令 \(m_1=\max\limits_{1\leq j< i}\left\{\frac{p_j-p_i}{a_i-a_j}\right\}\)，\(m_2=\min\limits_{i< j\leq n}\left\{\frac{p_j-p_i}{a_i-a_j}\right\}\)，也就是说，如果第 \(i\) 个函数满足 \(m_2>0\land m_2>m_1\)。那么第 \(i\) 个函数就会在某个时刻有最大值。是可以被统计入答案中的。（注意判断相同的函数以及在 \(t=0\) 处最大的这两种情况）

那么现在只需要求出 \(m_1,m_2\) 这一问题就可解了。现在考虑求出所有 \(i\) 的 \(m_1\)。

要求 \(\max\limits_{1\leq j< i}\left\{\frac{p_j-p_i}{a_i-a_j}\right\}\)，也就是求 \(-\min\limits_{1\leq j< i}\left\{\frac{p_i-p_j}{a_i-a_j}\right\}\)。也就是考虑如何求 \(i\) 以前所有点 \((a_j, p_j)\) 与点 \((a_i, p_i)\) 连线的斜率最小值。显然当这一点与 \(1\sim i-1\) 组成的点集上凸包相切的时候会有答案。因此开一个单调队列维护上凸包，查询时二分凸包即可。

求 \(m_2\) 用相似的过程倒着来一遍。

复杂度 \(O(t\cdot n\log n)\)。

Code

#include 
#define pii pair
#define fr first
#define sc second
#define a(i) (b[i].fr)
#define p(i) (b[i].sc)
using namespace std;
const int N = 50000+5;

int t, n, tot, kp[N], vis[N];
pii a[N], b[N];
int q[N], top, ANS;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n); tot = 0;
        for (int i = 1; i <= n; i++)
            scanf("%lld%lld", &a[i].sc, &a[i].fr);
        sort(a+1, a+n+1); a[n+1].fr = -1;
        for (int i = 1; i <= n; i++) 
            if (a[i].fr != a[i+1].fr) {
                if (a[i].fr != a[i-1].fr || a[i].sc != a[i-1].sc) {
                    b[++tot] = a[i], vis[tot] = 1;
                    
                }
                else if (a[i].fr == a[i-1].fr && a[i].sc == a[i-1].sc) b[++tot] = a[i], vis[tot] = 0;
            }
        n = tot; b[0].fr = b[1].fr-1, b[0].sc = -2147483647;
        top = 0;
        for (int i = 1; i <= n; i++) {
            int l = 1, r = top, ans = 0, m, j, k;
            while (l <= r) {
                m = (l+r)>>1, j = q[m], k = q[m-1];
                if (1ll*(p(i)-p(j))*(a(j)-a(k)) < 1ll*(p(j)-p(k))*(a(i)-a(j))) ans = m, l = m+1;
                else r = m-1;
            }
            kp[i] = q[ans];
            while (top && 1ll*(p(i)-p(q[top]))*(a(q[top])-a(q[top-1])) >= 1ll*(p(q[top])-p(q[top-1]))*(a(i)-a(q[top]))) --top;
            q[++top] = i;
        }
        if (n) ANS = vis[n];
        else ANS = 0;
        b[0].fr = 1ll+b[n].fr;
        q[top = 1] = n;
        for (int i = n-1; i >= 1; i--) {
            int l = 1, r = top, ans = top, m, j, k;
            while (l <= r) {
                m = (l+r)>>1, j = q[m], k = q[m-1];
                if (1ll*(p(i)-p(j))*(a(j)-a(k)) > 1ll*(p(j)-p(k))*(a(i)-a(j))) ans = m, l = m+1;
                else r = m-1;
            }
            int x = kp[i], y = q[ans];
            if (p(i) > p(y) && 1ll*(p(i)-p(x))*(a(y)-a(i)) > 1ll*(p(i)-p(y))*(a(x)-a(i))) ANS += vis[i];
            while (top && 1ll*(p(i)-p(q[top]))*(a(q[top])-a(q[top-1])) <= 1ll*(p(q[top])-p(q[top-1]))*(a(i)-a(q[top]))) --top;
            q[++top] = i;
        }
        printf("%d\n", ANS);
    }
    return 0;
}