题目描述
blablabla
样例
include[HTML_REMOVED]
using namespace std;
int a[1000001];
int temp[1000001];
long long sum = 0;
void verse_count( int l,int r)
{
if(l >=r)
return ;
int mid = l + r >>1;
verse_count( l, mid);
verse_count( mid + 1, r);
int i = l, j = mid + 1,k = 0;
while(i <= mid && j <= r)
{
if(a[i] > a[j])
{
sum = sum + mid-i+1;
temp[ k++] = a[j ++];
}
else
{
temp[ k++] = a[i ++];
}
}
while(i <= mid ) {
temp[ k++] = a[i++];
}
while(j <= r ) temp[ k++] = a[j++];
for(i=l,j=0; i <=r; i++,j++) a[i] =temp[j ];
}
int main()
{
int n;
cin >> n;
for(int i = 0; i <n; i ++)
cin >> a[i];
verse_count( 0,n-1);
cout << sum;
}
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla