求助替罪羊树
  • 板块学术版
  • 楼主Vizzi_02
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/5/7 17:47
  • 上次更新2023/10/28 01:58:55
查看原帖
求助替罪羊树
341396
Vizzi_02楼主2022/5/7 17:47

如何判断rank和kth输入数据不合法

//我的写法
int getRank(int x,int v)
{  
	if(x == 0)	return 0;
	if(v == tr[x].dat)
	{
		fl = 1;
		return tr[lc(x)].sz+1;
	}
	if(v > tr[x].dat) return getRank(rc(x),v)+tr[lc(x)].sz+tr[x].cnt; 
	if(v < tr[x].dat) return getRank(lc(x),v);
}
int getKth(int x, int k) 
{
  if(x == 0) return -1;
  if (tr[lc(x)].sum + 1 <= k && k <= tr[lc(x)].sum + tr[x].sz )
  	return tr[x].dat;
  if (k > tr[lc(x)].sum)
  	return getKth(rc(x),k - tr[lc(x)].sum - tr[x].cnt);
  else
  	return getKth(lc(x),k);
  
}
int main()
{
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		char op;
		int r;
		cin >> op;
		cin >> r;
		if(op == 'I') insert(root,r);
		if(op == 'R')
		{
			int t = getRank(root,r);
			if(!fl)
				cout << -1 << endl;
			else
				cout << t << endl;
			fl = 0;
		}
		else if(op == 'K')
		{
			cout << getKth(root,r) << endl;
		}
	}
}
2022/5/7 17:47
加载中...