题目大意

维护一个向量集合，在线支持以下操作：

"A x y (|x|，|y| < =10^8)"：加入向量(x，y);

"Q x y l r (|x|，|y| < =10^8，1 < =L < =R < =T，其中T为已经加入的向量个数)询问第L个到第R个加入的向量与向量(x，y)的点积的最大值。

集合初始时为空。

分析

题目中相当于给出一堆点\((z,w)\)

询问点\(x,y\)

求\(maximize(ans=xz+yw)\)

\(\frac {ans} y=\frac x y z+w\)

\(w=-\frac x y z+\frac {ans} y\)

相当于函数\(w=f(z)=-\frac x y z+\frac {ans} y\)

就是一条斜率为\(-\frac x y\),截距为\(\frac {ans} y\)的线

对于一次询问中,斜率不变，截距记为\(D\)

①y>0，我们要使ans尽可能大，则截距尽可能大，答案在上凸壳

②y<0，我们要使ans尽可能大，则截距尽可能小，答案在下凸壳

③y=0，我们要使ans尽可能大，则xz尽可能大，z只会在最左最右，而最左最右的点一定在凸壳上，所以在上下凸壳找都行

做法

线段树维护凸包+三分

当然不能每插入一个点都合并一下

注意到一个没有插满的线段是不会被询问的

所以只有当插入位置为线段右端点时，将线段上的点搞一个凸包

每条线段合并一次，每条线段上有恰好\(r-l+1\)个点

所以每层n个点，凸包\(n\log n\)，总共\(\log n\)层

总复杂度\(n \log^2 n\)

注意

1.三分时要保证函数中没有重点，不然会有\(bug\)

2.\(ans\)可能为负，所以取\(max\)时的初始值为\(-INF\)

3.线段树大小为比\(n*2\)大的一个二进制数

4.数组大小为\(n*(\log n +1)+1\)

小结

扫描线的思维是找单调性，判断答案是否在凸包上的一种好方法

这种题只是说答案在凸包上，实际和凸包没有太大的关联

所以我们不必要先搞出询问区间的凸包再三分

只需要分段取出答案再取max就好了

solution

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          typedef long long LL;using namespace std;const int M=1048576;const int N=10485763;const LL INF=9223372036854775807;LL rd(){ LL x=0;bool f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=0; for(;isdigit(c);c=getchar()) x=x*10+c-48; return f?x:-x;}struct pt{ LL x,y; pt (LL _x=0.0,LL _y=0.0){x=_x;y=_y;}};bool operator <(pt x,pt y){return (x.x!=y.x)?(x.x
          
           
            1&&side(up[x].s[up[x].top-1],up[x].s[up[x].top],a[i])>=0) up[x].top--; up[x].s[++up[x].top]=a[i]; } dw[x].rsz(tp); for(i=1;i<=tp;i++){ while(dw[x].top>1&&side(dw[x].s[dw[x].top-1],dw[x].s[dw[x].top],a[i])<=0) dw[x].top--; dw[x].s[++dw[x].top]=a[i]; }}LL gmx(int x,pt d){ arr &nw=(d.y>0)?up[x]:dw[x]; int l=1,r=nw.top,m1,m2,i; LL tp1,tp2; while(r-l>=3){ m1=(l+l+r)/3; m2=(r+l+r)/3; tp1=dot(nw.s[m1],d); tp2=dot(nw.s[m2],d); if(tp1
            
             >1; if(to<=mid) ins(x<<1,l,mid,to,d); else ins(x<<1|1,mid+1,r,to,d); addedge(x,d); if(r==to) convex(x);}LL get(int x,int l,int r,int tl,int tr,pt d){ if(tl<=l&&r<=tr) return gmx(x,d); int mid=l+r>>1; LL res=-INF; if(tl<=mid) res=max(res,get(x<<1,l,mid,tl,tr,d)); if(mid