2299:Ultra-QuickSort （树状数组求逆序对）

el/2023/6/3 16:18:20

题目来源：http://bailian.openjudge.cn/practice/2299?lang=en_US

Ultra-QuickSort

查看
提交
统计
提示
提问

总时间限制:

7000ms

内存限制:

65536kB

描述

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence

9 1 0 5 4 ,

Ultra-QuickSort produces the output

0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

输入

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

输出

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

样例输入

样例输出

6
0

裸的一个树状数组题

关于树状数组： https://blog.csdn.net/qq_41431457/article/details/88945833

#include<bits/stdc++.h>
using namespace std;
using lom = long long;const int M = 500005;
int a[M], b[M], t[M], n;int lowbit(int x)
{return x & -x;
}int add(int x)//把包含这个数的结点都更新 
{while(x <= n)//范围 {t[x]++;x += lowbit(x);}
}int sum(int x)//查询1~X有几个数加进去了 
{int res = 0;while(x >= 1){	res +=t [x];x -= lowbit(x);}return res;
}bool cmp(int x, int y)
{if(a[x] == a[y]) return x > y;return a[x] > a[y];
}int main()
{while(cin >> n && n){memset(t, 0, sizeof t);lom ans = 0;for(int i = 1; i <= n; i++){scanf("%d", a + i);b[i] = i;}sort(b + 1, b + n + 1, cmp);for(int i = 1; i <= n; i++){add(b[i]);ans += sum(b[i] - 1);}cout << ans << endl;}return 0;
}

归并排序版：

#include<bits/stdc++.h>
#define M 500005
using namespace std;
int a[M],t[M],n;
long long ans=0;
void msort(int l,int r)
{if(l==r) return ;int mid=l+r>>1;msort(l,mid);	msort(mid+1,r);int i=l, j=mid+1, k=l;while(i<=mid&&j<=r)if(a[i]<=a[j]) t[k++]=a[i++];else t[k++]=a[j++], ans+=mid-i+1;while(i<=mid) t[k++]=a[i++];while(j<=r)   t[k++]=a[j++];for(int i=l;i<=r;i++) a[i]=t[i];
}
int main()
{
//	freopen("in.txt","r",stdin);while(cin>>n && n){ans = 0;for(int i=1;i<=n;i++) cin>>a[i];msort(1,n);	cout << ans << endl;}return 0;
}