[HDU 6759]Leading Robots

3932 ワード

Description


ライブラリリンク
(n)個の二次関数(f_i(t)=frac{1}{2}a_を与えるit^2+p_i\).質問関数(g(t)=maxlimits_{1leq ileq n}{f_i(t)},tin[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}foralljeq i,exists t_0,&frac{ 1}{2}a_it_0^2+p_i>frac{ 1}{2}a_jt_0^2+p_j\Righarrow&frac{ 1}{2}t_0^2(a_i-a_j)>p_j-p_i\Righarrow&left{ begin{aligned}{1}{2}t_0^2}t_0^2(a_i-a_j)>p_i\Righarrow&left{ begin{align frac{1}{2}t_0^2>frac{p_j-p_i}{a_i-a_j},&i>j\frac{1}{2}t_0^2
命令(m_1=maxlimits_{1leq j0land m_2>m_1)を満たす場合.では、(i)番目の関数は、ある時点で最大値を有します.答えに集計できます.(注意同じ関数を判断する場合と、(t=0)で最大となる場合の2つ)
では、今は(m_1,m_2)という問題を求めるだけで解けます.すべての(i)の(m_1)を求めることを考えます.
要求(maxlimits_{1leq j求めて(m_2)似たような過程で逆さまに1回来ます.
複雑度(O(tcdot nlog 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
", ANS); } return 0; }