樹狀數組 之 冒泡排序（詳細分析）

題目描述

clj 想起當年自己剛學冒泡排序時的經曆，不禁思緒萬千

當年，clj 的冒泡排序(僞)代碼是這樣的:

flag=false
while (not flag):
   flag=true
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         flag=false
           

現在的 clj 想知道冒泡排序究竟有多慢，是以在(僞)代碼的第三行下面加入了這

麼一句:

printf(“LJS NB\n”);

但是随着需要排序的 個數越來越多，這個程式的速度已經不能滿足 clj 的耐心了

他想請你幫忙算出這個程式到底能輸出多少行LJS NB

輸入格式

第一行一個數 ，表示 數組有 個數;

接下來一行共 個數,用空格隔開，表示 數組的每一個元素。

輸出格式

一行一個整數，表示這個程式會輸出多少行 LJS NB。

樣例

輸入樣例1

5

1 5 3 8 2

輸出樣例1

4

代碼

#include<cstdio>
#include<algorithm>
using namespace std;
const int M=2*1e6+5;
int discre[M],Bit[M],a[M];
int n;
void Discretetion(){	
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		discre[i]=a[i];
	}
	sort(discre+1,discre+1+n);
	int tot=unique(discre+1,discre+1+n)-discre-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(discre+1,discre+tot+1,a[i])-discre;
	}
}
long long lowbit(int x){
	return x & (-x);
}
void update(int x){
	for(int i=x;i<=n;i+=lowbit(i)){
		Bit[i]++;
	}
} 
long long Sum(int x){
	long long tot=0;
	for(int i=x;i>0;i-=lowbit(i)){
		tot+=Bit[i];
	}
	return tot;
}
int main(){
	Discretetion();
	long long tmax=0;
	for(int i=1;i<=n;i++){
		update(a[i]);
		tmax=max(tmax,i-Sum(a[i]));
	}
	printf("%lld",tmax+1);
	return 0;
}