bzoj 3533 [Sdoi2014]向量集 凸包

和2961求的是一个东西。

维护上下两个凸包，然后三分。

上次写得是一个正常的线段树，填满一个区间就合并。

这次写了一个奇怪的按二进制维护log棵类线段树状物的东西，然后发现跑得比线段树慢。。。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 810000
const ll inf=~lu>>;
int Q,l,r,top,cnt,n,num,xq,yq;
char opt[],s[];
ll ans;
int X[N],Y[N],p[N*],ch[N][];
int st[],size[N],L[N],R[N],mx[N],mn[N];
int beg1[N],ed1[N],beg2[N],ed2[N];
ll getk(int p1,int p2,int p3)
{return (ll)(X[p2]-X[p1])*(Y[p3]-Y[p2])-(ll)(X[p3]-X[p2])*(Y[p2]-Y[p1]);}
void dec(int &x)
{
    if(opt[]=='E')return;
    x=x^(ans& );
}
void ins1(int x,int v)
{
    while(num-beg1[x]>=&&getk(p[num-],p[num],v)>=)
        num--;
    p[++num]=v;
}
void ins2(int x,int v)
{
    while(num-beg2[x]>=&&getk(p[num-],p[num],v)<=)
        num--;
    p[++num]=v;
}
int merge(int x,int y)
{
    int ret=++cnt,l1,l2;
    ch[ret][]=x;ch[ret][]=y;
    L[ret]=L[x];R[ret]=R[y];
    mx[ret]=max(mx[x],mx[y]);
    mn[ret]=min(mn[x],mn[y]);
    size[ret]=size[x]+size[y];

    beg1[cnt]=num+;
    l1=beg1[x],l2=beg1[y];
    while(l1<=ed1[x]&&l2<=ed1[y])
    {
        int t1=p[l1],t2=p[l2];
        if(X[t1]<X[t2]||(X[t1]==X[t2]&&Y[t1]<Y[t2]))
            ins1(cnt,t1),l1++;
        else ins1(cnt,t2),l2++;
    }
    while(l1<=ed1[x])
        ins1(cnt,p[l1]),l1++;
    while(l2<=ed1[y])
        ins1(cnt,p[l2]),l2++;
    ed1[cnt]=num;

    beg2[cnt]=num+;
    l1=beg2[x],l2=beg2[y];
    while(l1<=ed2[x]&&l2<=ed2[y])
    {
        int t1=p[l1],t2=p[l2];
        if(X[t1]<X[t2]||(X[t1]==X[t2]&&Y[t1]>Y[t2]))
            ins2(cnt,t1),l1++;
        else ins2(cnt,t2),l2++;
    }
    while(l1<=ed2[x])
        ins2(cnt,p[l1]),l1++;
    while(l2<=ed2[y])
        ins2(cnt,p[l2]),l2++;
    ed2[cnt]=num;

    return ret;
}
void newnode(int x,int y)
{
    X[++n]=x;Y[n]=y;
    st[++top]=++cnt;size[cnt]=;
    beg1[cnt]=ed1[cnt]=++num;p[num]=n;
    beg2[cnt]=ed2[cnt]=++num;p[num]=n;
    L[cnt]=R[cnt]=n;mx[cnt]=mn[cnt]=x;

    while(top>&&size[st[top]]==size[st[top-]])
        st[top-]=merge(st[top-],st[top]),top--;
}
ll getv(int x){return (ll)xq*X[x]+(ll)yq*Y[x];}
void proc(int x)
{
    if(yq==)
    {
        ans=max(ans,(ll)xq*mx[x]);
        ans=max(ans,(ll)xq*mn[x]);
    }
    else
    {   
        int l,r;
        if(yq>)l=beg1[x],r=ed1[x];
        else l=beg2[x],r=ed2[x];
        while(r-l>=)
        {
            int lm=(l+l+r)/,rm=(l+r+r)/;
            if(getv(p[lm])<getv(p[rm]))l=lm;
            else r=rm;
        }
        for(int i=l;i<=r;i++)
            ans=max(ans,getv(p[i]));
    }
}
void query(int x)
{
    if(!x||r<L[x]||l>R[x])return;
    if(l<=L[x]&&R[x]<=r)
        {proc(x);return;}
    query(ch[x][]);query(ch[x][]);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%s",&Q,opt+);
    for(int x,y;Q--;)
    {
        scanf("%s",s+);
        if(s[]=='A')
        {
            scanf("%d%d",&x,&y);
            dec(x);dec(y);
            newnode(x,y);
        }
        else
        {
            scanf("%d%d%d%d",&x,&y,&l,&r);
            dec(x);dec(y);dec(l);dec(r);
            ans=-inf;xq=x;yq=y;
            for(int i=,t;i<=top;i++)
                query(st[i]);
            printf("%lld\n",ans);
        }
    }
    return ;
}