트 리 배열 역순 맞 추기

역순 을 구 하 는 데 가장 자주 사용 하 는 방법 은 바로 나무 모양 의 배열 이다. 확실히 나무 모양 의 배열 은 매우 우수한 알고리즘 이다.POJ 2299 를 만 들 때 이 알고리즘 을 접 했 는데 이해 하기 가 어 려 웠 습 니 다. 그러면 다음 에 제 가 생각 을 정리 하 겠 습 니 다.
우선: 제목 에서 a [i] 는 999, 999, 999 의 많 기 때문에 트 리 배열 을 사용 할 때 사용 하 는 트 리 배열 C [i] 는 비트 저장 소 와 비슷 한 배열 을 바탕 으로 하 는 것 이지 단순히 입력 배열 위 에 세 워 진 것 이 아니다.예 를 들 어 9, 1, 0, 5, 4 (최대 9) 를 입력 하면 C [i] 트 리 배열 의 구축 은 다음 과 같다. 아래 에 표 시 된 0, 1, 2, 3, 4, 5, 6, 7, 8 – 아래 표 시 는 9 배열 로 만들어 야 한다. 1, 0, 1, 0, 1 을 통 해 현재 99999999 라 는 숫자 가 500000 이라는 숫자 에 비해 매우 크기 때문에 배열 로 저장 하면...그러면 입력 한 데 이 터 를 저장 하기 위해 99999999 의 공간 이 필요 하 다.공간 을 낭비 하고 제목 도 허용 되 지 않 기 때문에 이산 화 작업 을 통 해
그럼 어떻게 이산 화 작업 을 합 니까?이산 화 는 흔히 사용 하 는 기법 이다. 때로는 데이터 범위 가 너무 커서 우리 가 처리 할 수 있 는 범 위 를 좁 힐 수 있다. 필요 한 것 은 구조 체 a [n] 를 구축 하 는 것 이다. v 는 입력 의 값 을 표시 하고 order 는 원 i 값 을 표시 하 며 하나의 배열 aa [n] 로 이산 화 된 값 을 저장 하 는 것 이다..order]=i; aa: 5 1, 2, 4, 3 즉 원래 의 9 는 순 서 를 거 쳐 5 위 에 있어 야 합 니 다. 현재 aa [1] = 5 는 원래 의 9 에 대응 하고 크기 순 서 는 변 하지 않 으 며 9 를 5 로 줄 였 습 니 다.
그러면 이산 화 된 후에 어떻게 역순 을 구 합 니까?솔직히 저 는 오래 생각 했 습 니 다. 먼저 update 함 수 를 통 해 하나의 수 를 삽입 하 는 것 입 니 다. 예 를 들 어 update (2, 1) 는 처음에 c [n] 이 0 이 고 삽입 후 + 1 입 니 다. 현재 나머지 는 0, c [2], c [4] = 1 입 니 다. 이것 은 앞 에 2 로 표시 되 어 있 는 숫자 2 가 있 습 니 다. 여기 가 관건 입 니 다. c [4] = 1 은 아래 에 4 로 표시 되 었 을 때 하나의 숫자 4 가 있 는 것 이 아니 라 4 이전 구간 에 있 는 모든 요소 의 합 이 1 이라는 뜻 입 니 다.즉, 하나의 수 2 가 있 습 니 다. 구체 적 으로 트 리 그림 을 볼 수 있 습 니 다. 그 다음 에 getsum 으로 하나의 수 를 삽입 하 는 앞 에 몇 개의 수 를 구하 면 현재 이 수 보다 작은 수의 개 수 를 계산 할 수 있 습 니 다. 그리고 아래 표 시 된 i - getsum (aa [i]) 을 통 해 그 보다 큰 수 를 얻 을 수 있 습 니 다. 즉, 역순 수 입 니 다.예: 1, 5 를 입력 하고 upDate (5, 1) 를 호출 하여 5 위 를 1, 2, 3, 4, 50, 0 1 로 설정 하여 1 - 5 에서 5 보다 작은 숫자 가 존재 합 니까?트 리 배열 의 getSum (5) = 1 작업 을 사 용 했 습 니 다. 현재 입력 한 아래 표 시 된 1 - getSum (5) = 0 으로 5 에 대한 역순 수 를 0 으로 얻 을 수 있 습 니 다.2. 2 를 입력 하고 upDate (2, 1) 를 호출 하여 2 위 를 1, 2, 3, 4, 0, 1, 0 1 / / 로 설정 합 니 다. 여기 서 실제 출력 하 는 것 은 0, 1, 1 입 니 다. 그러나 위 에서 말 한 것 처럼 여기 서 진정한 의 미 는 2 만 삽입 하 는 것 입 니 다. c [4] 는 앞의 c [2] 변화 로 인해 변화 하 는 것 입 니 다. 그리고 변화 가 있어 도 괜 찮 습 니 다. 뒤의 getsum 을 통 해 구 하 는 항상 구간 의 합, 뒤에 계산 할 때 c [4] 의 값 만 계산 합 니 다.앞 에는 더 하지 않 고 c [4] 의 값 은 바로 앞 에서 4 까지 이기 때문에 나타 난 숫자 와 계산 1 - 2 에 2 보다 작은 숫자 가 존재 합 니까?트 리 배열 의 getSum (2) = 1 동작 을 사 용 했 습 니 다. 현재 입력 한 아래 표 시 된 2 - getSum (2) = 1 을 사용 하면 2 에 대한 역순 수 를 1 로 얻 을 수 있 습 니 다.
POJ 2299 코드 는 다음 과 같 습 니 다.

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn= 500005;
int aa[maxn];//       
int c[maxn]; //    
int n;

struct Node
{
    int v;
    int order;
}a[maxn];

bool cmp(Node a, Node b)
{
    return a.v < b.v;
}

int lowbit(int k)
{
    return k&(-k); //   lowbit   
}

void update(int t, int value)
{     //      0，      （+1），
    int i;
    for (i = t; i <= n; i += lowbit(i))
        c[i] += value;  
}

int getsum(int t)
{  //       ，              
    int i, sum = 0;
    for (i = t; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}

int main()
{
    int i;
    while (scanf("%d", &n), n)
    {
        for (i = 1; i <= n; i++) //   
        {
            scanf("%d", &a[i].v);
            a[i].order = i;
        }
        sort(a + 1, a + n + 1,cmp);// 1 n  ,cmp   
        memset(c, 0, sizeof(c));
        for (i = 1; i <= n; i++)
            aa[a[i].order] = i;
        __int64 ans = 0;
        for (i = 1; i <= n; i++)
        {
            update(aa[i], 1);
            ans += i - getsum(aa[i]); //                 
        }
        printf("%I64d
", ans);
    }
    return 0;
}