BZOJ3938 & UOJ88：[集训队互测2015]Robot—

https://www.lydsy.com/JudgeOnline/problem.php?id=3938

小q有n只机器人，一开始他把机器人放在了一条数轴上，第i只机器人在ai的位置上静止，而自己站在原点。在这之后小q会执行一些操作，他想要命令一个机器人向左或者向右移动x格。但是机器人似乎听不清小q的命令，事实上它们会以每秒x格的速度匀速移动。看着自己的机器人越走越远，小q很着急，他想知道当前离他（原点）最远的机器人有多远。具体的操作以及询问见输入格式。注意，不同的机器人之间互不影响，即不用考虑两个机器人撞在了一起的情况。

显然机器人的运动是一个分段一次函数，故可以李超线段树维护之。

然而t很大，所以需要离散化，但是为了答案的正确性，我们需要存真的斜率和截距。

于是参考了其他人的代码，加上自己的码风，将原来的板子又推翻重建，变成了现在这个模样，应该很好看。

#include<map>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

#define fi first

#define se second

const int N=1e5+;

const int M=5e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

vector<pii>a[N];

int t[N+M],q[M],lim,n,m;

char s[];

struct node{

    int l,r;

    ll k,b;

    node(int L=,int R=,ll K=,ll B=){

    l=L,r=R,k=K,b=B;

    }

    ll point(int x){return k*x+b;}

}mx[(N+M)*],mn[(N+M)*];

inline int LSH(int x){

    return lower_bound(t+,t+lim+,x)-t;

}

ll query(int a,int l,int r,int k){

    ll a1=abs(mx[a].point(t[k])),a2=abs(mn[a].point(t[k]));

    if(l==r)return max(a1,a2);

    int mid=(l+r)>>;ll ans;

    if(k<=mid)ans=query(a<<,l,mid,k);

    else ans=query(a<<|,mid+,r,k);

    return max(ans,max(a1,a2));

}

void upt(int a,int l,int r,node k){

    int mid=(l+r)>>;

    if(k.point(t[mid])>mx[a].point(t[mid]))swap(k,mx[a]);

    if(l==r)return;

    if(min(mx[a].point(t[l]),mx[a].point(t[r]))>=max(k.point(t[l]),k.point(t[r])))return;

    if(mx[a].k>k.k)upt(a<<,l,mid,k);

    else upt(a<<|,mid+,r,k);

}

void dwn(int a,int l,int r,node k){

    int mid=(l+r)>>;

    if(k.point(t[mid])<mn[a].point(t[mid]))swap(k,mn[a]);

    if(l==r)return;

    if(max(mn[a].point(t[l]),mn[a].point(t[r]))<=min(k.point(t[l]),k.point(t[r])))return;

    if(mn[a].k<=k.k)dwn(a<<,l,mid,k);

    else dwn(a<<|,mid+,r,k);

}

void insert(int a,int l,int r,node k){

    if(r<k.l||k.r<l)return;

    if(k.l<=l&&r<=k.r){

        upt(a,l,r,k);dwn(a,l,r,k);

        return;

    }

    if(l==r)return;

    int mid=(l+r)>>;

    insert(a<<,l,mid,k);insert(a<<|,mid+,r,k);

}

int main(){

    n=read(),m=read();

    for(int i=;i<=n;i++)a[i].push_back(pii(,read()));

    t[++lim]=;

    for(int i=;i<=m;i++){

        int x=read();t[++lim]=x;scanf("%s",s);

        if(s[]=='c'){

        int id=read(),v=read();

        a[id].push_back(pii(x,v));

        }else q[++q[]]=x;

    }

    for(int i=;i<=n;i++)a[i].push_back(pii(1e9,));

    t[++lim]=1e9;

    sort(t+,t+lim+);

    lim=unique(t+,t+lim+)-t;

    for(int i=;i<=n;i++){

        int sz=a[i].size();

        ll now=a[i][].se;

        node p=node(LSH(a[i][].fi),LSH(a[i][].fi),,now);

        insert(,,lim,p);

        for(int j=;j<sz-;j++){

        int l=a[i][j].fi,r=a[i][j+].fi,k=a[i][j].se;

        p=node(LSH(l),LSH(r),k,now-(ll)k*l);

        insert(,,lim,p);

        now=now+(ll)k*(r-l);

        }

    }

    for(int i=;i<=q[];i++)

        printf("%lld\n",query(,,lim,LSH(q[i])));

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ3938 & UOJ88：[集训队互测2015]Robot——题解

最新文章

热门文章