L2 - 012. 더미 에 대한 판단 (데이터 구조)

L2 - 012. 더미 에 대한 판단
시간 제한
400 ms
메모리 제한
65536 kB
코드 길이 제한
8000 B
문제 풀이 절차
Standard
저자.
진 월
주어진 숫자 순 서 를 초기 에 비어 있 는 작은 지붕 더미 H [] 에 삽입 합 니 다.뒤이어 일련의 관련 명제 가 사실 인지 아 닌 지 를 판단 하 다.명 제 는 다음 과 같은 몇 가지 로 나 뉜 다.
"x is the root": x 는 뿌리 결점 이다
"x and y are siblings": x 와 y 는 형제 결점 입 니 다
"x is the parent of y": x 는 y 의 아버지 결점 이다
"x is a child of y": x 는 y 의 키 결점 이다
입력 형식:
각 조 의 테스트 첫 번 째 줄 은 2 개의 정수 N (< = 1000) 과 M (< = 20) 을 포함 하 는데 각각 요 소 를 삽입 하 는 개수 와 판단 해 야 할 명제 수 이다.다음 줄 은 구간 [- 1000, 10000] 에 있 는 N 개가 비어 있 는 작은 지붕 더미 의 정 수 를 삽입 해 야 합 니 다.그 다음 에 M 줄 은 줄 마다 명 제 를 제시한다.문 제 는 명제 의 결점 키 가 모두 존재 한 다 는 것 을 보증한다.
출력 형식:
입력 한 모든 명제 가 사실 이 라면 한 줄 에 'T' 를 출력 하고 그렇지 않 으 면 'F' 를 출력 합 니 다.
입력 예시:

5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10

출력 예시:

F
T
F
T

제출 코드
분석: 문 제 는 어렵 지 않 습 니 다 ~ 하지만 큰 구덩이 가 있 습 니 다. 한 번 에 모든 수 를 배열 에 넣 은 다음 에 더 미 를 업데이트 할 수 없습니다. 한 번 에 업데이트 해 야 합 니 다 ~ ~ ~
쌓 아 올 린 다음 에 각 수의 위 치 를 기록 합 니 다.
그리고 결합 관계.  오른쪽 아들 은 2 * x + 1) 결과 획득
AC 코드:

#include
using namespace std;
int node[200000];
int pre[200000]={0};
void swap(int &a,int &b)
{
	int t;
	t=a;
	a=b;
	b=t;
}
void update(int x,int len)
{
	int t=x;
	if(x*2>len) return;
	if(node[x]>node[x*2])
	t=t*2;
	if(x*2+1<=len&&node[t]>node[x*2+1])
	t=x*2+1;
	if(t==x) return;
	swap(node[x],node[t]);
	update(t,len);
}
void buildtree(int len)
{
	for(int i=len/2;i>=1;i--)
	{
		update(i,len);
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	memset(node,-1,sizeof(node));
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&node[i]);
		node[i]+=10000;
		buildtree(i);
	}
	//buildtree(n);
	for(int i=1;i<=n;i++)
	pre[node[i]]=i;
	while(m--)
	{
		int a,c;
		scanf("%d",&a);
		a+=10000;
		char b[100];
		scanf("%s",b);
		if(b[0]=='a')
		{
			scanf("%d",&c);
			c+=10000;
			scanf("%s%s",b,b);
			if(pre[a]/2==pre[c]/2&&pre[a]!=pre[c])
			printf("T
");
			else
			printf("F
");
		}
		else
		{
			scanf("%s",b);
			if(b[0]=='a')
			{
				scanf("%s%s",b,b);
				scanf("%d",&c);
				c+=10000;
				if(pre[c]*2==pre[a]||pre[c]*2+1==pre[a])
				printf("T
");
				else
				printf("F
");
			}
			else
			{
				scanf("%s",b);
				if(b[0]=='r')
				{
					if(pre[a]==1) 
					printf("T
");
					else
					printf("F
");
				}
				else
				{
					scanf("%s",b);
					scanf("%d",&c);
					c+=10000;
					if(pre[a]==pre[c]/2)
					printf("T
");
					else
					printf("F
");
				}
			}
		}
	}
}