为什么我的rebuild挂掉了

P4148 简单题

huhao @ 2019-03-14 15:32:19

#define N 200010
#define rbf 0.9
#define rbi 20
int m,n,s[N][2],x[N],y[N],c[N],t,ans,v[N],r,w[N],p[N],e,rb,rbo;
struct reb
{
    int x,y,v;
}a[N];
int cmp1(reb a,reb b)
{
    return a.x<b.x;
}
int cmp0(reb a,reb b)
{
    return a.y<b.y;
}
void del(int k,int o)
{
    if(!k)
        return;
    e++;
    a[e].x=x[k];
    a[e].y=y[k];
    a[e].v=v[k];
    del(s[k][0],1);
    del(s[k][1],1);
    if(o)
        c[++t]=k;
    x[k]=y[k]=s[k][0]=s[k][1]=w[k]=v[k]=p[k]=0;
}
int build(int l,int r,int o)
{
    if(l>r)
        return 0;
    int k;
    if(t)
    {
        k=c[t];
        t--;
    }
    else
        k=++n;
    if(o)
        nth_element(a+l,a+(l+r)/2,a+r+1,cmp1);
    else
        nth_element(a+l,a+(l+r)/2,a+r+1,cmp0);
    x[k]=a[(l+r)/2].x;
    y[k]=a[(l+r)/2].y;
    v[k]=a[(l+r)/2].v;
    p[k]=r-l+1;
    s[k][0]=build(l,(l+r)/2-1,o^1);
    s[k][1]=build((l+r)/2+1,r,o^1);
    w[k]=w[s[k][0]]+w[s[k][1]]+v[k];
    return k;
}
void rebuild(int k,int o)
{
    e=0;
    del(k,0);
    if(o)
        nth_element(a+1,a+e/2,a+e+1,cmp1);
    else
        nth_element(a+1,a+e/2,a+e+1,cmp0);
    x[k]=a[e/2].x;
    y[k]=a[e/2].y;
    v[k]=a[e/2].v;
    p[k]=e;
    s[k][0]=build(1,e/2-1,o^1);
    s[k][1]=build(e/2+1,e,o^1);
    w[k]=w[s[k][0]]+w[s[k][1]]+v[k];
}
void insert(int k,int o,int _x,int _y,int _v)
{
    int op;
    w[k]+=_v;
    if(x[k]==_x&&y[k]==_y)
    {
        v[k]+=_v;
        return;
    }
    p[k]++;
    if(o)
        op=(_x>=x[k]);
    else
        op=(_y>=y[k]);
    if(!s[k][op])
    {
        if(t)
        {
            s[k][op]=c[t];
            t--;
        }
        else
        {
            n++;
            s[k][op]=n;
        }
        k=s[k][op];
        x[k]=_x;
        y[k]=_y;
        v[k]=w[k]=_v;
        p[k]=1;
    }
    else
        insert(s[k][op],o^1,_x,_y,_v);
    if(p[k]>rbi&&(p[k]*rbf<p[s[k][0]]*1.||p[k]*rbf<p[s[k][1]]*1.))
    {
        rb=k;
        rbo=o;
    }
}
int query(int k,int o,int _x,int _y,int xx,int yy,int qx,int qy,int qxx,int qyy)
{
    if(_x>qxx||xx<qx||_y>qyy||yy<qy||k==0)
        return 0;
    if(_x>=qx&&xx<=qxx&&_y>=qy&&yy<=qyy)
        return w[k];
    int r=0;
    if(x[k]>=qx&&x[k]<=qxx&&y[k]>=qy&&y[k]<=qyy)
        r=v[k];
//  printf("%d %d %d (%d %d) (%d %d %d %d) (%d %d %d %d)\n",r,k,o,x[k],y[k],_x,_y,xx,yy,qx,qy,qxx,qyy);
    if(o)
        return r+query(s[k][0],o^1,_x,_y,x[k]-1,yy,qx,qy,qxx,qyy)+query(s[k][1],o^1,x[k],_y,xx,yy,qx,qy,qxx,qyy);
    else
        return r+query(s[k][0],o^1,_x,_y,xx,y[k]-1,qx,qy,qxx,qyy)+query(s[k][1],o^1,_x,y[k],xx,yy,qx,qy,qxx,qyy);
}
int main()
{
    m=read();
    while(1)
    {
        int opt=read();
        if(opt==3)
            break;
        if(opt==1)
        {
            int _x=read()^ans,_y=read()^ans,_v=read()^ans;
            rb=0;
            if(!n)
            {
                r=n=1;
                x[r]=_x;
                y[r]=_y;
                v[r]=w[r]=_v;
                p[r]=1;
            }
            else
                insert(r,1,_x,_y,_v);
            if(rb)
                rebuild(rb,rbo);
        }
        if(opt==2)
        {
            int _x=read()^ans,_y=read()^ans,_xx=read()^ans,_yy=read()^ans;
//          printf("%d %d %d %d\n",_x,_y,_xx,_yy);
            ans=query(r,1,1,1,m,m,_x,_y,_xx,_yy);
            printf("%d\n",ans);
        }
//      print(1);
//      putchar(10);
    }
    return 0;
}

by huhao @ 2019-03-14 16:09:55

坐标可以相同,本帖完结


by ecnerwaIa @ 2019-03-14 16:15:47

山前留名


|