【集训队互测2015】Robot

mrsrz 9月 24, 2020

线段树分治，李超树

题目大意：

给定 $n$ 个一次函数，初始时都只有常数项。

有两个操作：

修改某个一次函数。
给定 $x$，查询此时所有一次函数的值中，距离原点的最远距离（即绝对值最大的那个）。

共 $C$ 次修改和 $Q$ 次查询。

题解：

某个一次函数在一段时间里出现，容易想到线段树分治。

线段树分治的时候需要维护一次函数的最值。不难想到用李超树维护。

李超树可以撤回上一次操作，只要记录上一次操作修改了哪些点即可，每次不超过 $O(\log n)$ 个。

全局插入的李超树是单次 $O(\log n)$ 的，因此总时间复杂度为 $O((n+C)\log C\log Q + Q\log Q)$。

空间复杂度 $O(Q+(n+C)\log C)$。

Code：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5,M=6e5+5;
vector<int>T_A;
vector<pair<int,int> >Q[N];
struct stra{
    int k;LL b;
    inline LL get(int x)const{return(LL)k*x+b;}
}g[N];
struct data{
    int l,r,k;LL b;
};
struct lst{
    stra v;int nxt;
}e[N*60];
vector<data>K;
int n,m,w,T,beg[N],head[N<<2],cnt;
int top;
LL ans[M];
stra d[M<<2],pre[9000000];
int nid[9000000];
void add(int l,int r,int o,const int&L,const int&R,const int&k,const LL&b){
    if(L<=l&&r<=R){
        e[++cnt]=(lst){(stra){k,b},head[o]},head[o]=cnt;
    }else{
        const int mid=(l+r)/2;
        if(L<=mid)add(l,mid,o<<1,L,R,k,b);
        if(mid<R)add(mid+1,r,o<<1|1,L,R,k,b);
    }
}
void modify(int l,int r,int o,const stra&v){
    LL _L=d[o].get(T_A[l]),_R=d[o].get(T_A[r]);
    LL nL=v.get(T_A[l]),nR=v.get(T_A[r]);
    if(_L>=nL&&_R>=nR)return;
    if(_L<=nL&&_R<=nR){
        ++top;
        pre[top]=d[o],nid[top]=o;
        d[o]=v;
        return;
    }
    const int mid=(l+r)/2;
    modify(l,mid,o<<1,v),modify(mid+1,r,o<<1|1,v);
}
LL query(int l,int r,int o,const int&v){
    if(l==r)return d[o].get(T_A[v]);
    const int mid=(l+r)/2;
    if(v<=mid)return max(d[o].get(T_A[v]),query(l,mid,o<<1,v));
    return max(d[o].get(T_A[v]),query(mid+1,r,o<<1|1,v));
}
void solve(int l,int r,int o){
    int TOP=top;
    for(int i=head[o];i;i=e[i].nxt){
        const stra&x=e[i].v;
        modify(1,w,1,x);
    }
    if(l==r){
        for(int i=0;i<Q[l].size();++i){
            int id=Q[l][i].first,v=Q[l][i].second;
            int x=lower_bound(T_A.begin(),T_A.end(),v)-T_A.begin();
            ans[id]=max(ans[id],query(1,w,1,x));
        }
    }else{
        const int mid=(l+r)/2;
        solve(l,mid,o<<1),solve(mid+1,r,o<<1|1);
    }
    while(top>TOP)d[nid[top]]=pre[top],--top;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    T_A.push_back(-1);
    for(int i=1;i<=n;++i)cin>>g[i].b,beg[i]=1;
    T=1;
    for(int i=1;i<=m;++i){
        char cmd[23];
        int t;
        cin>>t>>cmd;
        if(*cmd=='c'){
            ans[i]=-1;
            int id,v;
            cin>>id>>v;
            K.push_back((data){beg[id],T,g[id].k,g[id].b});
            LL nw=(LL)g[id].k*t+g[id].b;
            LL nb=nw-(LL)t*v;
            beg[id]=++T;
            g[id]=(stra){v,nb};
        }else Q[T].push_back(make_pair(i,t)),T_A.push_back(t);
    }
    T_A.erase(unique(T_A.begin(),T_A.end()),T_A.end());
    w=(int)T_A.size()-1;
    for(int i=1;i<=n;++i)K.push_back((data){beg[i],T,g[i].k,g[i].b});
    for(int i=0;i<(int)K.size();++i)add(1,T,1,K[i].l,K[i].r,K[i].k,K[i].b);
    solve(1,T,1);
    for(int i=1;i<=cnt;++i)e[i].v.k*=-1,e[i].v.b*=-1;
    solve(1,T,1);
    for(int i=1;i<=m;++i)if(ans[i]!=-1)cout<<ans[i]<<'\n';
    return 0;
}