[나무 모양 배열] 파스칼 산맥.

1594 단어 데이터 구조트 리 배열
[제목 설명]
어린 카 카 는 노인 이 가리 키 는 방향 으로 파스칼 신봉 의 정상에 올 랐 다.노인 은 작은 카 카 에 게 파스칼 산맥 에는 많은 산 이 있 고 한 직선 위 에 있 으 며 산 마다 높이 가 다르다 고 말 했다.  Pascal 산 정상에 신기 한 동굴 이 있 습 니 다. 이 동굴 에 들 어가 면 이 산 앞 에 있 는 또 다른 산 에 도착 할 것 입 니 다. 더욱 신기 한 것 은 그 가 있 는 산 보다 높이 가 작 을 것 입 니 다.파스칼 성지 의 가장 큰 보물 은 파스칼 산 에 있 는 동굴 에 숨겨 져 있 는데 이 동굴 의 특징 은 석문 이 닫 혀 있다 는 것 이다.  작은 카 카 는 산 마다 동굴 로 들 어가 면 그 가 도착 하 는 산 이 얼마나 될 지 궁금 했다.
[형식 입력]
첫 번 째 줄 의 정수 n 은 산 의 개 수 를 나타 낸다. (1 < = n < = 20000)  두 번 째 줄 이후 n 행 은 앞 뒤로 모든 산 의 높이 를 제시한다.다른 두 산 은 같은 높이 를 가 질 수 있다. (1 = 각 산 의 높이 < = maxlongint) 
[출력 형식]
모두 n 행, 줄 마다 하나의 정수. I 행 의 정 수 는 그 가 I 호 산 동굴 에 들 어간 후에 도착 할 수 있 는 서로 다른 산 의 개 수 를 나타 낸다.
우 리 는 향 한 후에 나무 모양 의 배열 을 업데이트 합 니 다. 뒤의 것 이 더 작 으 면 반드시 앞 에 영향 을 주지 않 을 것 입 니 다. 산 의 높이 가 너무 높 습 니 다. 우 리 는 map 맵 을 사용 합 니 다.
매번 현재 보다 작은 것 을 먼저 조회 하고 업데이트 중 입 니 다.
#include
#include
#include
#include
#include
#include
using namespace std;
int n,a[20005],b[20005],cnt,tree[20005];
map ma;
int sum(int x)
{
	int ans=0;
	while(x)
	{
		ans+=tree[x];
		x-=(x&-x);
	}
	return ans;
}
void add(int x)
{
	while(x<=cnt)
	{
		tree[x]++;
		x+=(x&-x);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		if(!ma[a[i]]) ma[a[i]]=++cnt;
	}
	for(int i=1;i<=n;i++)
	{
		int now=ma[b[i]];
		printf("%d
",sum(now-1));
		add(now);
	}
}

TIL105. Django : Django Crontab 을 이용하기
데이터 구조 필기 정리 제6 장: 그림

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage