社区讨论

帮忙查个错,谢谢(72分)

P1801黑匣子参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo282ptd
此快照首次捕获于
2023/10/23 09:31
2 年前
此快照最后确认于
2023/11/03 09:46
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
int n,k,root,m,a[2000005],b;
struct tree{
	int l,r,w,tn;
	bool node;
	tree()
	{
		l=r=-1;
		node=false;
	}
}t[2000005];

void insert(int r,int y)
{
	if(!t[r].node)
	{
		t[r].w=y; t[r].tn=1; t[r].node=true;
		m++; t[r].l=m; m++; t[r].r=m;
		return;
	}
	t[r].tn++;
	if(y<t[r].w) insert(t[r].l,y);
	else if(y>t[r].w) insert(t[r].r,y);
	return;
}

void find(int x,int k)
{
	int ans=0;
	if(t[x].l==-1) ans=1;
	else ans=t[t[x].l].tn+1;
	if(k==ans) cout<<t[x].w<<endl;
	else if(k<ans) find(t[x].l,k);
	else find(t[x].r,k-ans);
}

int main()
{
	scanf("%d%d",&n,&b);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int last=1; m=1;
	for(int i=1;i<=b;i++)
	{
		int now;
		scanf("%d",&now);
		for(int j=last;j<=now;j++) insert(root,a[j]);
		find(root,i);
		last=now+1;
	}
	/*for(int i=1;i<=n;i++)
	{
		cout<<i<<" ";
		if(t[i].l!=-1&&t[t[i].l].w>0) cout<<"l:"<<t[i].l<<endl;
		if(t[i].r!=-1&&t[t[i].r].w>0) cout<<"r:"<<t[i].r<<endl;
	}*/
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...