HDU 5592(선분 수+2 분)

*********************************************************************************************************************************************************
오리지널 작품 은'효 풍 잔 월 xj'블 로그 에서 나 왔 습 니 다.전 재 를 환영 합 니 다.전재 할 때 반드시 출처 를 밝 혀 주 십시오(http://blog.csdn.net/xiaofengcanyuexj）。
여러 가지 이유 로 부족 한 점 이 많 을 수 있 습 니 다.수정 을 환영 합 니 다!
*********************************************************************************************************
ZYB's Premutation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 838 Accepted Submission(s): 403
Problem Description
ZYB has a premutation
P ,but he only remeber the reverse log of each prefix of the premutation,now he ask you to
restore the premutation.
Pair
(i,j)(iAi>Aj is matched.

Input
In the first line there is the number of testcases T.
For each teatcase:
In the first line there is one number
N .
In the next line there are
N numbers
Ai ,describe the number of the reverse logs of each prefix,
The input is correct.
1≤T≤5 ,
1≤N≤50000

Output
For each testcase,print the ans.

Sample Input

Sample Output

Source
BestCoder Round #65
이 문 제 는 각 위치 역순 수의 누적 갯 수 에 따라 수열 을 복원 해 야 한다.뒤에서 앞으로 밀어 현재 위치 요소 인 ans[i]의 앞 에 그 보다 크 거나 작은 요소 가 얼마나 있 는 지 구 할 수 있 습 니 다.ans[i]=log[i]-log[i-1 은 경계 처리 에 주의 하 십시오.그러나 앞 에 그 보다 크 거나 작은 요소 가 요소 의 크기 를 정확하게 정 하지 못 한 다 는 것 만 알 고 뒤에 그 보다 크 거나 작은 요 소 를 알 아야 합 니 다.
1)앞에서 그 보다 크 거나 작은 요소 의 개 수 는 역방향 으로 O(n)를 옮 겨 다 니 며 구 할 수 있다.
2)、뒤에 있 는 그 보다 크 거나 작은 요소 의 개 수 는 특정한 배열 에 가격 을 표시 한 다음 에 2 분 을 통 해 특정한 빠 른 구간 과 알고리즘-선분 트 리 를 결합 하여 시간 복잡 도 O(log(N)^2 를 얻 을 수 있 습 니 다.
이렇게 되면 전체 시간 복잡 도 는 O(N*log(N)이다. .오 랜 만 에 문 제 를 풀 었 습 니 다.템 플 릿 이 없 는 상황 에서 한 개의 선분 트 리 와 2 분 구 는 첫 번 째 요소 와 같은 코드 를 디 버 깅 한 지 오래 되 었 습 니 다.앞으로 이런 기본 코드 를 많이 두 드 려 야 할 것 같 습 니 다.업무 코드 만 쌓 는 것 이 아 닙 니 다.하하.

#include<cstdio>
#include<cstring>
#define MAXN 50000+10

int log[MAXN];
int ans[MAXN];

struct treeNode
{
	int l,r,sum;
}tree[MAXN*3];

void build(int id,int l,int r)
{
	tree[id].l=l,tree[id].r=r;
	if(l==r)
	{
		tree[id].sum=1;
		return ;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
}

void update(int pos,int id,int val)
{
	if(tree[id].l==tree[id].r)
	{
		tree[id].sum+=val;
		return ;
	}
	int mid=(tree[id].l+tree[id].r)>>1;
	if(pos<=mid)
	{
		update(pos,id<<1,val);
	}
	else
	{
		update(pos,id<<1|1,val);
	}
	tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
}

int query(int l,int r,int id)
{
	if(tree[id].l==l&&tree[id].r==r)
	{
		return tree[id].sum;
	}
	int mid=(tree[id].l+tree[id].r)>>1;
	if(r<=mid)
	{
		return query(l,r,id<<1);
	}
	else if(l>mid)
	{
		return query(l,r,id<<1|1);
	}
	return query(l,mid,id<<1)+query(mid+1,r,id<<1|1);
}

int main()
{
	int t;
	scanf("%d",&t);
	while(--t)
	{
		memset(tree,MAXN*sizeof(int),0);
		int n;
		scanf("%d",&n);
		log[0]=0;
		for(int i=1;i<=n;++i)
		{
			scanf("%d",&log[i]);
		}
		build(1,1,n);
		for(int j=n;j>0;--j)
		{
			int tmp=j-(log[j]-log[j-1])-1;
			int l=1,r=n;
			while(l<r)
			{
				int mid=(l+r)>>1;
			//	printf("tmp=%d  mid=%d l=%d  r=%d
",tmp,mid,l,r);
				if(query(l,mid,1)<=tmp)
				{
					l=mid+1;
				}
				else
				{
					r=mid;
				}
			}
			ans[j]=l;
		//	printf("%d  
",l);
			update(ans[j],1,-1);
		}
		for(int k=1;k<=n;++k)
		{
			printf("%d ",ans[k]);
		}
		printf("
");
	}
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 5592(선분 수+2 분)

좋은 웹페이지 즐겨찾기