P11728 [集训队互测 2015] Robot

· · 题解

先看测试点 6,7：不会在 t_i>0 时出现 command 操作，此时若以时间 t 为横坐标，机器人在数轴上的位置 x 为横坐标绘出机器人的轨迹，易知其为形如 x=kt+b 的一次函数图像。

但当 t_i>0 时出现 command 操作时，该轨迹又会变成一条折线，极为不美观，此时若把折线分成若干线段，则每条线段仍满足上面的性质，但有定义域的限制。

因此考虑离线，将每个机器人的轨迹分为若干线段存储，线段总数为 n+C（n 个机器人，每次操作会产生 1 个新的线段）。

现在题目转化为：

现有 n+C 条形如 x=kt+b,t \in[l,r] 的线段，Q 次询问，每次给定一个数 t_i，求与直线 t=t_i 相交的线段中，交点纵坐标最大为多少。

显然是李超线段树，但交点坐标均为整数，比模版P4097 【模板】李超线段树还是好写点的。

注意：

附代码：

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

#define ls tr[p].l
#define rs tr[p].r

typedef long long ll;
typedef long double ld;

const int N=1e5+10;

struct line{
    int k;ll b;
}p[N<<2];

int cnt=0;

ll f(int id,int x){
    return labs(1ll*p[id].k*x+p[id].b);
}

struct tree{
    int l,r,id;
}tr[N<<5];

int tot=0,rt=0;

void pushnow(int &p,int l,int r,int now){
    if(!p) p=++tot;
    int &lst=tr[p].id,mid=(l+r)>>1;
    if(f(now,mid)>f(lst,mid)) swap(now,lst);

    if(f(now,l)>f(lst,l)) pushnow(ls,l,mid,now);
    if(f(now,r)>f(lst,r)) pushnow(rs,mid+1,r,now);
}

void update(int &p,int l,int r,int ql,int qr,int now){
    if(!p) p=++tot;
    if(ql<=l&&r<=qr) return pushnow(p,l,r,now),void();
    int mid=(l+r)>>1;
    if(ql<=mid) update(ls,l,mid,ql,qr,now);
    if(qr>mid) update(rs,mid+1,r,ql,qr,now);
}

ll query(int p,int l,int r,int pl){
    if(!p) return 0;
    ll res=f(tr[p].id,pl);
    int mid=(l+r)>>1;
    if(pl<=mid) return max(res,query(ls,l,mid,pl));
    else return max(res,query(rs,mid+1,r,pl));
}

int n,m,mxt=0,a[N];

vector<pair<int,int> > ch[N];

vector<int> q;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ch[i].push_back({0,0});
    }
    int t,k,x; string s;
    for(int i=1;i<=m;i++){
        cin>>t>>s;
        mxt=max(mxt,t);
        if(s[0]=='c'){
            cin>>k>>x;
            if((*ch[k].rbegin()).first==t) ch[k].pop_back();
            ch[k].push_back({t,x});
        }
        else q.push_back(t);
    }
    for(int i=1;i<=n;i++){
        if((*ch[i].rbegin()).first!=mxt) ch[i].push_back({mxt,0});
        ll y=a[i];
        for(int j=1;j<(int)ch[i].size();j++){
            int l=ch[i][j-1].first,r=ch[i][j].first,k=ch[i][j-1].second;
            p[++cnt]={k,y-1ll*k*l};
            y+=1ll*(r-l)*k;
            update(rt,0,mxt,l,r,cnt);
        }
    }
    for(auto i:q)
        cout<<query(1,0,mxt,i)<<'\n';
    return 0;
}