达成成就：一人独霸三页提交

自己写的莫名其妙MLE死都不知道怎么回事，照着题解打一直RE一个点最后发现竟然是凸包上一个点求错了……四个半小时就一直用来调代码了……

那么我们只要维护好这个凸壳，因为这是一个凸函数，所以只要在上面三分找最值即可

于是现在我们需要维护一个资瓷插入的凸壳。考虑线段树，我们发现每一次在线段树上询问的区间必然都是已经把点插满了的。那么我们可以考虑线段树上每一个节点内的所有元素都插入完之后，再构建凸壳，那么显然每个节点只会被构建一次凸包，所以复杂度是\(O(nlog^2n)\)

然后注意一个细节……因为我们维护好的凸包要便于分成上下凸壳，所以凸包的起点应该是\(x\)坐标最小的，这样才满足它左右两边分别是上凸壳和下凸壳……我按照以前的写法找\(y\)坐标最小的当起点然后就没有然后了……

//minamoto#include
    
     #define fp(i,a,b) for(register int i=a,I=b+1;i
     
      I;--i)#define ll long long#define inf 1e18using namespace std;template
      
       inline bool cmax(T&a,const T&b){return a
       
        '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getchar())>='0'&&ch<='9';res=res*10+ch-'0');    res*=f;if(flag)res^=(lasans&0x7fffffff);    return res;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(ll x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=4e5+5;struct node{int x,y;}b[N],st[N];struct seg{    int l,r,pos,sz;seg *ch[2];    vector
        
         mp;}pool[N<<2],*rt;inline node operator -(node a,node b){return (node){a.x-b.x,a.y-b.y};}inline ll operator *(node a,node b){return 1ll*a.x*b.y-1ll*b.x*a.y;}inline ll dot(node a,node b){return 1ll*a.x*b.x+1ll*a.y*b.y;}inline bool operator <(node a,node b){    a=a-st[1],b=b-st[1];    return a*b==0?1ll*a.x*a.x+1ll*a.y*a.y<1ll*b.x*b.x+1ll*b.y*b.y:a*b>0;}void graham(seg *p){    int top=1,sz=p->r-p->l+1,k=1;    fp(i,1,sz)b[i]=p->mp[i-1];    fp(i,2,sz)if(b[i].x
         
          
           1&&(b[i]-st[top-1])*(st[top]-st[top-1])>=0)--top; st[++top]=b[i]; }st[++top]=b[1];p->sz=top; vector
           
            ().swap(p->mp);// p->mp.clear(); fp(i,1,top)p->mp.push_back(st[i]); fp(i,1,top-1)if(st[i+1].x<=st[i].x){p->pos=i-1;break;}}ll calc(seg *p,node q){ int l,r,m1,m2;ll ans=-inf; q.y>0?(l=p->pos,r=p->sz-1):(l=0,r=p->pos); while(r-l>=3){ m1=l+(r-l)/3,m2=r-(r-l)/3; dot(q,p->mp[m1])>dot(q,p->mp[m2])?r=m2:l=m1; }fp(i,l,r)cmax(ans,dot(q,p->mp[i]));return ans;}void ins(seg *p,int pos,node x){ p->mp.push_back(x);if(pos==p->r)graham(p);if(p->l==p->r)return; int mid=(p->l+p->r)>>1;pos<=mid?ins(p->ch[0],pos,x):ins(p->ch[1],pos,x);}ll query(seg *p,int l,int r,node x){ if(l<=p->l&&r>=p->r)return calc(p,x); int mid=(p->l+p->r)>>1;ll res=-inf; if(l<=mid)cmax(res,query(p->ch[0],l,r,x)); if(r>mid)cmax(res,query(p->ch[1],l,r,x)); return res;}void build(seg *p,int l,int r){ p->l=l,p->r=r;if(l==r)return;int mid=(l+r)>>1; build(p->ch[0]=pool+ ++all,l,mid),build(p->ch[1]=pool+ ++all,mid+1,r);}int main(){// freopen("testdata.in","r",stdin); int n,l,r,tot=0;char s[10];node x; n=read(),scanf("%s",s),flag=s[0]!='E'; build(rt=pool+ ++all,1,n); while(n--){ scanf("%s",s),x.x=read(),x.y=read(); if(s[0]=='Q')l=read(),r=read(),print(lasans=query(rt,l,r,x)); else ins(rt,++tot,x); }return Ot(),0;}