P3103 [USACO14FEB]Airplane Boarding G 题解

xixike · 2022-01-15 19:50:37 · 题解

更好的阅读体验

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) 对于以后所有的奶牛都是没有用的。

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