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
我的阳寿啊