POJ 2299 Ultra - QuickSort (트 리 배열 역순 구)

http://poj.org/problem?id=2299
나무 모양 의 배열 로 역 서 수 를 구 하 는 것 은 선분 나무 로 역 서 수 를 구 하 는 방법 과 유사 하 다.91054 를 입력 하면 C [i] 트 리 배열 의 구축 은 0, 1, 2, 3, 4, 5, 6, 79 배열 1, 0, 1, 0, 1, 0, 0, 1 을 표시 합 니 다.그래서 둘 다 이산 화가 필요 하 다.그리고 대충 생각 은 업 데 이 트 를 하면 서 값 을 구 하 는 거 예요.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;

const int N = 500000 + 100;
long long a[N],b[N];
long long n;
long long tr[N];
long long lowbit(long long x)
{
    return x & (-x);
}
void update(long long pos,long long val)
{
    while(pos<=n)
    {
        tr[pos] += val;
        pos += lowbit(pos);
    }
    return;
}
long long query(long long x)
{
    long long sum = 0;
    while(x)
    {
        sum += tr[x];
        x -= lowbit(x);
    }
    return sum;
}
long long solve()
{
    long long res = 0;
    for(long long i = n;i>=1;i--)
    {
        long long x = lower_bound(b+1,b+1+n,a[i])-(b+1) + 1;
        res += query(x-1);
        update(x,1);
    }
    return res;
}
int main()
{
    while(~scanf("%lld",&n) && n) 
    {
        memset(tr,0,sizeof(tr));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(long long i=1;i<=n;i++)
            scanf("%lld",&a[i]),b[i] = a[i];
        sort(b+1,b+1+n);
        printf("%lld
",solve());
    }
    return 0;
}

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

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

체인 테이블의 회문 여부를 판단하다

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

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

POJ 2299 Ultra - QuickSort (트 리 배열 역순 구)

좋은 웹페이지 즐겨찾기