[Extremely Easy] P11728 [集训队互测 2015] Robot

简要题意

给定 $n$ 个机器人，初始时第 $i$ 个机器人位于 $a_i$ 静止，依次进行有 $m$ 次操作，支持：

• t command k v 在第 $t$ 个时刻，将第 $k$ 个机器人的速度改为向正方向 $v$ 个单位每时刻。
• t query 询问机器人在第 $t$ 个时刻距离 $0$ 的最大距离。

$0\leq t\leq 10^9,1\leq n\leq 10^5,1\leq m\leq 6\times 10^5$，保证 $t$ 递增。

思路

根据小学行程问题可知，对于一次 command 操作，假设当前位于 $p$，若接下来没有 command 操作，则对于 $t'\geq t$，$t$ 时刻的位置为 $p+v(t'-t)=vt'+(p-vt)$，这是一个一次函数的形式。

与原点的距离可以看成坐标绝对值，则要求所有一次函数在 $x=t$ 的绝对值最大值，不妨将每个一次函数的取各常数相反数，改为求普通的最大值。那么这显然是一个（大概率）可以用李超线段树解决的问题。

对于原问题，我们需要修改一个一次函数，查询 $x=t$ 的一次函数最大值。修改可以拆成插入和删除，李超线段树很容易支持插入，但不容易做删除。所以可以用线段树分治，每次记录插入时改变的位置即可。时间复杂度 $O(m\log m\log V)$。

注意实现细节，否则你可能会挂在 UOJ 的 Hack 数据。

代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

template<int N, class T, class Cmp>
struct lichao_sgt {
    struct node{
        T k, b;
        T operator()(T x){ return k * x + b; }
    };

    stack<pair<int,node>> history;

    node t[N];
    int tot, ls[N], rs[N], fa[N];
    Cmp cmp;
    T lim = max(numeric_limits<T>::max(), numeric_limits<T>::min(), cmp);

    void update(node x, int& i, int l, int r){
        if(!i) i = ++tot, t[i].k = 0, t[i].b = lim;
        if(l == r){
            if(cmp(x(l), t[i](l))) history.emplace(i, t[i]), t[i] = x;
            return;
        }
        int mid = (l + r) >> 1;
        if(cmp(x(mid), t[i](mid))) history.emplace(i, t[i]), swap(x, t[i]);
        if(cmp(x(l), t[i](l))) update(x, ls[i], l, mid), fa[ls[i]] = i;
        if(cmp(x(r), t[i](r))) update(x, rs[i], mid + 1, r), fa[rs[i]] = i;
    }

    T query(int p, int i, int l, int r){
        if(!i) return lim;
        if(l == r) return t[i](p);
        int mid = (l + r) >> 1;
        if(p <= mid) return min(query(p, ls[i], l, mid), t[i](p), cmp);
        else return min(query(p, rs[i], mid + 1, r), t[i](p), cmp);
    }

    void rollback(int x){
        while(x--) t[history.top().first] = history.top().second, history.pop();
    }

    void free(int x){
        if(ls[fa[x]] == x) ls[fa[x]] = 0;
        else rs[fa[x]] = 0;
        ls[x] = rs[x] = fa[x] = 0;
    }
};

const int N = 1e5 + 5, Q = 6e5 + 5;
vector<pair<i64,i64>> t[Q << 2];
lichao_sgt<N * 35, i64, greater<i64>> sgt;
int root, timt[Q];
i64 answer[Q];

void update(int ql, int qr, pair<i64,i64> v, int i, int l, int r){
    if(ql <= l && r <= qr) return t[i].push_back(v), void();
    int mid = (l + r) >> 1;
    if(ql <= mid) update(ql, qr, v, i << 1, l, mid);
    if(mid < qr) update(ql, qr, v, i << 1 | 1, mid + 1, r);
}

void solve(int i, int l, int r){
    size_t hist = sgt.history.size();
    int tt = sgt.tot;
    for(auto &[x, y] : t[i]){
        sgt.update({x, y}, root, 0, 1e9);
    }
    if(l == r){
        if(~timt[l]) answer[l] = sgt.query(timt[l], root, 0, 1e9);
    }
    else solve(i << 1, l, (l + r) >> 1), solve(i << 1 | 1, ((l + r) >> 1) + 1, r); sgt.rollback(sgt.history.size() - hist);
    while(sgt.tot > tt) sgt.free(sgt.tot--);
    if(!sgt.tot) root = 0;
}

int n, m;
pair<pair<i64,i64>,int> info[N];

pair<i64,i64> negative(pair<i64,i64> x){ return {-x.first, -x.second}; }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        int pos; cin >> pos;
        info[i] = {{0, pos}, 1};
    }
    fill(timt + 1, timt + m + 2, -1);
    for(int i=1;i<=m;i++){
        i64 t, x, y; string s;
        cin >> t >> s;
        if(s == "command"){
            cin >> x >> y;
            update(info[x].second, i, info[x].first, 1, 1, m + 1);
            update(info[x].second, i, negative(info[x].first), 1, 1, m + 1);
            i64 pos = info[x].first.first * t + info[x].first.second;
            info[x] = {{y, pos - y * t}, i + 1};
        }
        else timt[i + 1] = t;
    }
    for(int i=1;i<=n;i++){
        update(info[i].second, m + 1, info[i].first, 1, 1, m + 1);
        update(info[i].second, m + 1, negative(info[i].first), 1, 1, m + 1);
    }
    solve(1, 1, m + 1);
    for(int i=1;i<=m+1;i++){
        if(~timt[i]) cout << answer[i] << '\n';
    }
    return 0;
}

// Written by xiezheyuan

Submission。