破案了!

P4148 简单题

whileAK @ 2024-05-05 16:50:57

当有重复元素时,nth_element会把相同的元素随机放在左右两侧,也就是左右子树都有与当前节点维度坐标相同的元素,此时两边都要递归。如下:

80pts:

if(t[p].w){
        if(lx<=t[p].x)ans=ask(lx,rx,ly,ry,t[p].ls);
        if(rx>t[p].x)ans+=ask(lx,rx,ly,ry,t[p].rs);
    }
    else{
        if(ly<=t[p].y)ans=ask(lx,rx,ly,ry,t[p].ls);
        if(ry>t[p].y)ans+=ask(lx,rx,ly,ry,t[p].rs);
    }

100pts:

if(t[p].w){
        if(lx<=t[p].x)ans=ask(lx,rx,ly,ry,t[p].ls);
        if(rx>=t[p].x)ans+=ask(lx,rx,ly,ry,t[p].rs);
    }
    else{
        if(ly<=t[p].y)ans=ask(lx,rx,ly,ry,t[p].ls);
        if(ry>=t[p].y)ans+=ask(lx,rx,ly,ry,t[p].rs);
    }

送一个小样例(没有强制在线的):

500000

1 9 4 8

2 3 5 6 7

1 4 8 10

2 3 5 6 7

1 10 5 5

2 3 5 6 7

1 2 7 3

2 3 5 6 7

1 6 7 3

2 3 5 6 7

1 4 3 2

2 3 5 6 7

1 2 4 6

2 3 5 6 7

3

输出: 0

0

0

0

3

3

3

我的阳寿啊


|