P3103 [USACO14FEB]Airplane Boarding G 题解(P3103 [usaco14feb] aircraft boarding g problem solution)

\(Description\)

Luogu传送门

\(Solution\)

偶然发现这道题所以来做做。

刚开始看完题的时候感觉这只能暴力模拟……

于是不要脸的看了一眼题解之后,我们可以用一些表达式来表示每头奶牛到达它应该到的位置的时间,从而计算出总共时间。

具体来说,第 \(n\) 头牛到达其位置所用时间是 \(s_n + t_n\),第 \(n – 1\) 头牛到达 \(s_n\) 的时间就是 \(s_n + t_n + 1\)(因为 \(cow_{n – 1}\) 初始坐标比 \(cow_n\) 的坐标靠左 1)

所以我们可以用二元组 \((pos_i, time_i)\) 来表示一头牛到达 \(pos_i\) 所花的时间为 \(time_i\),对于一头牛有许多这样的二元组来限制它。

那么这只牛走到目的地的时间就是 \(\max\{time_i + (S – pos_i)\} + T\),二元组满足条件 \(pos_i \leq S\)。

我们再把 \(S\) 提出来,所以要找的就是 \(time_i – pos_i\) 的最大值。

但是目前复杂度还是 \(n^2\) 的,我们还要考虑如何优化。

不难发现,对于两个二元组限制条件 \((a, b)\) 和 \((c, d)\),如果 \(a < c\) 且 \(d – c < b – a\),那么 \((c, d)\) 对于以后所有的奶牛都是没有用的。

\(d – c < b – a\) 使得 \((c, d)\) 对于当前的奶牛没有贡献,再加上 \(a < c\) 使得 \((c, d)\) 这个条件对于后面所有的奶牛都没有了贡献。

所以我们直接把这个条件删掉即可。

用平衡树维护一下 \(pos\) 和 \(time – pos\) 的值,以及 \(time – pos\) 的最大值,倒序枚举每一头奶牛:

  • 查询:把 \(pos \leq S_i\) 的数切下来查询。
  • 修改:当前插入的二元组是 \((a, b)\),然后把树中 \(d – c > b – a\) 的点全都删掉。

然后就没别的了,具体见代码吧。

我写的 fhq-treap

\(Code\)

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
int n;
int S[N], T[N];

namespace FHQ_treap{
    #define ls(x) t[x].l
    #define rs(x) t[x].r

    struct tree{
        int sum, wei, l, r, x, y, val, tag;
    }t[N];
    int root, tot;

    inline void pushup(int x){
        if(!x) return;
        t[x].val = t[x].y;
        if(ls(x)) t[x].val = max(t[x].val, t[ls(x)].val);
        if(rs(x)) t[x].val = max(t[x].val, t[rs(x)].val);
    }

    inline void pushdown(int x){
        if(!x || !t[x].tag) return;
        int tag = t[x].tag;
        if(ls(x)){
            t[ls(x)].x -= tag, t[ls(x)].y += tag;
            t[ls(x)].tag += tag, t[ls(x)].val += tag;
        }
        if(rs(x)){
            t[rs(x)].x -= tag, t[rs(x)].y += tag;
            t[rs(x)].tag += tag, t[rs(x)].val += tag;
        }
        t[x].tag = 0;
    }

    inline void split_pos(int x, int k, int &a, int &b){
        if(!x) return a = b = 0, void();
        pushdown(x);
        if(k >= t[x].x) a = x, split_pos(rs(x), k, rs(x), b);
        else b = x, split_pos(ls(x), k, a, ls(x));
        pushup(x);
    }

    inline void split_val(int x, int k, int &a, int &b){
        if(!x) return a = b = 0, void();
        pushdown(x);
        if(k >= t[x].y) a = x, split_val(rs(x), k, rs(x), b);
        else b = x, split_val(ls(x), k, a, ls(x));
        pushup(x);
    }

    inline int merge(int x, int y){
        if(!x || !y) return x | y;
        if(t[x].wei <= t[y].wei){
            pushdown(x);
            rs(x) = merge(rs(x), y);
            return pushup(x), x;
        }else{
            pushdown(y);
            ls(y) = merge(x, ls(y));
            return pushup(y), y;
        }
    }

    inline int newnode(int a, int b){
        t[++tot].x = a, t[tot].y = t[tot].val = b, t[tot].wei = rand();
        return tot;
    }
}
using namespace FHQ_treap;

int main(){
    n = read();
    for(int i = 1; i <= n; ++i)
        S[i] = read(), T[i] = read();
    int ans = 0, a, b, c;
    root = newnode(0, 0);
    for(int i = n; i >= 1; --i){
        split_pos(root, S[i], a, b);
        int res = t[a].val + S[i] + T[i];
        ans = max(ans, res);
        t[a].tag++, t[a].x--, t[a].y++, t[a].val++;//奶牛初始坐标向左依次减 1,对于 (a, b) 来说相当于变成了 (a - 1, b)
        split_val(b, res + 1 - S[i], b, c);
        root = merge(a, merge(newnode(S[i], res + 1 - S[i]), c));
    }
    write(ans), puts("");
    return 0;
}
————————

\(Description\)

Luogu portal

\(Solution\)

I found this problem by chance.

When I first finished reading the question, I felt that it could only be simulated by violence

So after a shameless look at the problem solution, we can use some expressions to express the time when each cow reaches its position, so as to calculate the total time.

Specifically, the time taken for the \ (n \) cow to reach its position is \ (s_n + t_n \), and the time for the \ (n – 1 \) cow to reach \ (s_n + t_n + 1 \) (because the initial coordinate of \ (cow_{n – 1} \) is 1 to the left of the coordinate of \ (cow_n \)

Therefore, we can use the binary \ ((pos_i, time_i) \) to represent that the time taken for a cow to reach \ (pos_i \) is \ (time_i \), and there are many such binary for a cow to limit it.

Then the time when the cow reaches its destination is \ (\ Max \ {time_i + (s – pos_i) \} + T \), and the binary satisfies the condition \ (pos_i \ Leq s \).

We propose \ (s \) again, so what we are looking for is the maximum value of \ (time_i – pos_i \).

However, the complexity is still \ (n ^ 2 \), and we need to consider how to optimize it.

It is not difficult to find that for the two binary constraints \ ((a, b) \) and \ ((C, d) \), if \ (A & lt; C \) and \ (D – C & lt; B – a \), then \ ((C, D) \) is useless for all cows in the future.

\(D – C & lt; B – a \) makes \ ((C, d) \) no contribution to the current cow. In addition, \ (A & lt; C \) makes \ ((C, d) \) no contribution to all the following cows.

So we can just delete this condition.

Maintain the values of \ (POS \) and \ (time – POS \) and the maximum value of \ (time – POS \) with the balance tree, and enumerate each cow in reverse order:

  • Query: cut off the number of \ (POS \ Leq s_i \) and query.
  • Modify: the currently inserted binary is \ ((a, b) \), and then delete all the points of \ (D – C > b – a \) in the tree.

Then there’s nothing else. See the code for details.

I wrote fhq Treap

\(Code\)

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
int n;
int S[N], T[N];

namespace FHQ_treap{
    #define ls(x) t[x].l
    #define rs(x) t[x].r

    struct tree{
        int sum, wei, l, r, x, y, val, tag;
    }t[N];
    int root, tot;

    inline void pushup(int x){
        if(!x) return;
        t[x].val = t[x].y;
        if(ls(x)) t[x].val = max(t[x].val, t[ls(x)].val);
        if(rs(x)) t[x].val = max(t[x].val, t[rs(x)].val);
    }

    inline void pushdown(int x){
        if(!x || !t[x].tag) return;
        int tag = t[x].tag;
        if(ls(x)){
            t[ls(x)].x -= tag, t[ls(x)].y += tag;
            t[ls(x)].tag += tag, t[ls(x)].val += tag;
        }
        if(rs(x)){
            t[rs(x)].x -= tag, t[rs(x)].y += tag;
            t[rs(x)].tag += tag, t[rs(x)].val += tag;
        }
        t[x].tag = 0;
    }

    inline void split_pos(int x, int k, int &a, int &b){
        if(!x) return a = b = 0, void();
        pushdown(x);
        if(k >= t[x].x) a = x, split_pos(rs(x), k, rs(x), b);
        else b = x, split_pos(ls(x), k, a, ls(x));
        pushup(x);
    }

    inline void split_val(int x, int k, int &a, int &b){
        if(!x) return a = b = 0, void();
        pushdown(x);
        if(k >= t[x].y) a = x, split_val(rs(x), k, rs(x), b);
        else b = x, split_val(ls(x), k, a, ls(x));
        pushup(x);
    }

    inline int merge(int x, int y){
        if(!x || !y) return x | y;
        if(t[x].wei <= t[y].wei){
            pushdown(x);
            rs(x) = merge(rs(x), y);
            return pushup(x), x;
        }else{
            pushdown(y);
            ls(y) = merge(x, ls(y));
            return pushup(y), y;
        }
    }

    inline int newnode(int a, int b){
        t[++tot].x = a, t[tot].y = t[tot].val = b, t[tot].wei = rand();
        return tot;
    }
}
using namespace FHQ_treap;

int main(){
    n = read();
    for(int i = 1; i <= n; ++i)
        S[i] = read(), T[i] = read();
    int ans = 0, a, b, c;
    root = newnode(0, 0);
    for(int i = n; i >= 1; --i){
        split_pos(root, S[i], a, b);
        int res = t[a].val + S[i] + T[i];
        ans = max(ans, res);
        t[a].tag++, t[a].x--, t[a].y++, t[a].val++;//奶牛初始坐标向左依次减 1,对于 (a, b) 来说相当于变成了 (a - 1, b)
        split_val(b, res + 1 - S[i], b, c);
        root = merge(a, merge(newnode(S[i], res + 1 - S[i]), c));
    }
    write(ans), puts("");
    return 0;
}