题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
include [HTML_REMOVED]
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int q[N];
int temp[N];
int n;
LL mergeSort(int q[], int l, int r)
{
if (l >= r)
{
return 0;
}
int mid = l + r >> 1;
LL res = mergeSort(q,l, mid) + mergeSort(q,mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <=mid &&j<=r)
{
if (q[i] <= q[j])
{
temp[k++] = q[i++];
}
else
{
temp[k++] = q[j++];
res += mid - i + 1;
}
}
while (i <= mid)
{
temp[k++] = q[i++];
}
while (j <= r)
{
temp[k++] = q[j++];
}
for (int i = l, j = 0; i <= r; i++, j++)
{
q[i] = temp[j];
}
return res;
}
//
//int func(int q[], int l, int r)
//{
// int count = 0;
// while (l < r)
// {
// for (int i = r; i > l; i–)
// {
// if (q[l] > q[i])
// {
// count;
// }
// }
// l;
// }
// return count;
//}
//
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> q[i];
}
cout << mergeSort(q,0, n - 1);
}