poj 2299 - Ultra - QuickSort (역순 구)

제목: 길이 가 n 인 서열 을 제시 하고 매번 에 인접 한 두 가지 요소 만 교환 할 수 있 으 며 적어도 몇 번 은 교환 해 야 이 서열 을 증가 서열 로 만 들 수 있 습 니 다.
우 리 는 역순 수 = 인접 한 두 요소 만 교환 할 수 있 는 조건 에서 질서 있 는 서열 의 교환 횟수 를 얻 을 수 있다 는 것 을 알 아야 한다.
그래서 우 리 는 수열 의 역순 수 를 구 해 야 한다. O (N * N) 의 알고리즘 은 반드시 시간 을 초과 할 것 이다.
모든 우리 가 비교적 효율 적 인 정렬 방법 을 찾 고 정렬 하 는 것 은 분 치 법 을 충분히 이용 하여 효율 을 높이 는 정렬 방법 이다.
병합 정렬:

#include <cstdio>
#define M  500005
int n , s[M];
long long ans;
void move(int l, int mid, int r)
{
    int len = r-l+1;
    int *a = new int[len+2];
    int li = l, ri = mid+1, i = 1;
    for(; li<=mid&&ri<=r;)
        if(s[li]<=s[ri]) a[i++] = s[li++];
        else
        {
            a[i++] = s[ri++];
            ans+=(mid-l+1-li+l);
        }
    while(li<=mid) a[i++] = s[li++];
    while(ri<=r) a[i++] = s[ri++];
    for(int j = 1; j <= len; ++j)
        s[j+l-1] = a[j];
    delete a;
}
void merge(int l, int r)
{
    if(l>=r) return;
    int mid = l+(r-l)/2;
    merge(l,mid);
    merge(mid+1,r);
    move(l, mid, r);
}
int main ()
{
    while(scanf("%d",&n), n)
    {
        for(int i = 1; i <= n; ++i)
            scanf("%d",&s[i]);
        ans = 0;
        merge(1,n);
        printf("%I64d
",ans);
    }
    return 0;
}

우 리 는 또 나무 모양 의 배열 로 그 역 서 수 를 구 할 수 있다.
트 리 배열:
트 리 배열 을 처음 접 했다 면 참고 하 세 요.http://blog.csdn.net/q573290534/article/details/6664902
이산 화 + 트 리 배열, = = > 역순 수 를 구하 십시오.
사고: 분 산 된 배열 [9 1 0 5 4] = > [ 5 2 1 4 3] 역순 으로 상 태 를 갱신 하면,
예컨대
1. 3 으로 시작 하 는 역순 수 를 찾 으 면 3 보다 작은 모든 숫자 를 찾 는 개수 입 니 다.그리고 3 을 배열 에 삽입 합 니 다 [0]
2. 4 로 시작 하 는 역순 수 를 찾 아 4 【 1 】 업데이트
3. 1 로 시작 하 는 역순 수 를 찾 아 1 【 0 】 을 업데이트 합 니 다.
4、。。。2。。。。。【1】
5、。。。5。。。。。【4】
마지막 정 답 은 [1 + 1 + 4 = 6]
코드 는 다음 과 같 습 니 다:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 500005
#define lowbit(x) x&-x
struct Node{
    int v, x;
};
Node a[M];
int n, r[M], tree[M];
int comp(const Node p, const Node q) { return p.v<q.v; }
void update(int x)
{
    while(x<=n)
    {
        tree[x]+=1;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int ret = 0;
    while(x>0)
    {
        ret+=tree[x];
        x-=lowbit(x);
    }
    return ret;
}
int main ()
{
    int t;
    while(scanf("%d",&n), n)
    {
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d",&t);
            a[i].v = t;
            a[i].x = i;
        }
        sort(a+1,a+1+n,comp);
        for(int i = 1; i <= n; ++i)
            r[a[i].x] = i;

        long long ans = 0;
        memset(tree,0,sizeof(tree));
        for(int i = n; i >= 1; i--)
        {
            ans+=sum(r[i]);
            update(r[i]);
        }
        printf("%I64d
",ans);
    }
    return 0;
}