(题目链接)

题意

　　给出数轴上$n$个点，有$m$个操作，在时间$t$让一个点以一定的速度移动，或者询问时间$t$时距离原点最远的点。

Solution

　　超哥线段树。时间当做横坐标，负半轴的情况斜率和截距乘上$-1$再做一遍。

　　话说我为什么要离散化=  =

细节

　　LL

代码

// bzoj3938#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define LL long long#define inf (1ll<<60)#define eps 1e-8#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=1000010;LL ans[maxn],a[maxn];int n,m,cnt,tot,last[maxn],tim[maxn],q[maxn];char ch[100];struct seg { LL k,b,l,r; LL ch(LL x) {return k*x+b;}}v[maxn];struct node {int cov;seg mx;}tr[maxn<<2];double X(seg a,seg b) { return a.k==b.k ? inf : 1.0*(a.b-b.b)/(b.k-a.k);}void insert(int k,int l,int r,int s,int t,seg g) { int mid=(l+r)>>1; if (l==s && r==t) { if (!tr[k].cov) tr[k].mx=g,tr[k].cov=1; else { seg a1=tr[k].mx,a2=g;double x=X(a1,a2); if (a1.ch(tim[l])
           
            =tim[r]) {tr[k].mx=a1;return;} if (x<=tim[mid]) tr[k].mx=a2,insert(k<<1,l,mid,s,mid,a1); else tr[k].mx=a1,insert(k<<1|1,mid+1,r,mid+1,t,a2); } return; } if (t<=mid) insert(k<<1,l,mid,s,t,g); else if (s>mid) insert(k<<1|1,mid+1,r,s,t,g); else insert(k<<1,l,mid,s,mid,g),insert(k<<1|1,mid+1,r,mid+1,t,g);}LL query(int k,int l,int r,int x) { if (l==r) return tr[k].cov ? tr[k].mx.ch(x) : 0; int mid=(l+r)>>1;LL t=0; if (x<=tim[mid]) t=query(k<<1,l,mid,x); else t=query(k<<1|1,mid+1,r,x); return tr[k].cov ? max(t,tr[k].mx.ch(x)) : t;}void clear(int k,int l,int r) { tr[k].cov=0; if (l==r) return; int mid=(l+r)>>1; clear(k<<1,l,mid); clear(k<<1|1,mid+1,r);}int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); for (int i=1;i<=n;i++) v[++cnt]=(seg){0,a[i],0,-1},last[i]=cnt; for (int x,i=1;i<=m;i++) { scanf("%d",&tim[i]); scanf("%s",ch); if (ch[0]=='c') { scanf("%d%lld",&x,&v[++cnt].k); v[last[x]].r=v[cnt].l=tim[i];v[cnt].r=-1; a[x]=v[last[x]].k*tim[i]+v[last[x]].b; v[cnt].b=a[x]-v[cnt].k*tim[i]; last[x]=cnt; } if (ch[0]=='q') q[++tot]=tim[i]; } m=unique(tim,tim+1+m)-tim-1; for (int i=1;i<=cnt;i++) { if (v[i].r==-1) v[i].r=tim[m]; int l=lower_bound(tim,tim+1+m,v[i].l)-tim; int r=lower_bound(tim,tim+1+m,v[i].r)-tim; insert(1,0,m,l,r,v[i]); } for (int i=1;i<=tot;i++) ans[i]=query(1,0,m,q[i]); clear(1,0,m); for (int i=1;i<=cnt;i++) { int l=lower_bound(tim,tim+1+m,v[i].l)-tim; int r=lower_bound(tim,tim+1+m,v[i].r)-tim; v[i].k*=-1;v[i].b*=-1; insert(1,0,m,l,r,v[i]); } for (int i=1;i<=tot;i++) ans[i]=max(ans[i],query(1,0,m,q[i])); for (int i=1;i<=tot;i++) printf("%lld\n",ans[i]); return 0;}