破案了!
  • 板块P4148 简单题
  • 楼主whileAK
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/5 16:50
  • 上次更新2024/5/5 19:17:43
查看原帖
破案了!
817925
whileAK楼主2024/5/5 16:50

当有重复元素时,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

我的阳寿啊

2024/5/5 16:50
加载中...