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

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

阅读量：6801 次

发布时间：2019-06-26

本文共 2393 字，大约阅读时间需要 7 分钟。

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

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

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

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

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long ll;typedef pair
                
                  pii;#define fi first#define se secondconst int N=1e5+10;const int M=5e5+10;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}vector
                 
                  a[N];int t[N+M],q[M],lim,n,m;char s[20];struct node{ int l,r; ll k,b; node(int L=0,int R=0,ll K=0,ll B=0){ l=L,r=R,k=K,b=B; } ll point(int x){ return k*x+b;}}mx[(N+M)*4],mn[(N+M)*4];inline int LSH(int x){ return lower_bound(t+1,t+lim+1,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)>>1;ll ans; if(k<=mid)ans=query(a<<1,l,mid,k); else ans=query(a<<1|1,mid+1,r,k); return max(ans,max(a1,a2));}void upt(int a,int l,int r,node k){ int mid=(l+r)>>1; 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<<1,l,mid,k); else upt(a<<1|1,mid+1,r,k);}void dwn(int a,int l,int r,node k){ int mid=(l+r)>>1; if(k.point(t[mid])
                  
                   >1; insert(a<<1,l,mid,k);insert(a<<1|1,mid+1,r,k);}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i].push_back(pii(0,read())); t[++lim]=0; for(int i=1;i<=m;i++){ int x=read();t[++lim]=x;scanf("%s",s); if(s[0]=='c'){ int id=read(),v=read(); a[id].push_back(pii(x,v)); }else q[++q[0]]=x; } for(int i=1;i<=n;i++)a[i].push_back(pii(1e9,0)); t[++lim]=1e9; sort(t+1,t+lim+1); lim=unique(t+1,t+lim+1)-t; for(int i=1;i<=n;i++){ int sz=a[i].size(); ll now=a[i][0].se; node p=node(LSH(a[i][0].fi),LSH(a[i][1].fi),0,now); insert(1,1,lim,p); for(int j=1;j