题目描述
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 = 100010;
int q[N];
int temp[N];
int n;
LL mergeSort(int l,int r)
{
if(l>=r)
{
return 0;
}
int mid=l+r>>1;
LL res = mergeSort(l,mid)+mergeSort(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(i=l,j=0;i<=r;i++,j++)
{
q[i]=temp[j];
}
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> q[i];
}
cout << mergeSort(0, n - 1);
}