NYOJ117&& 樹狀數組求逆序數
(轉)樹狀數組可以用來求逆序數， 當然一般用歸並求。如果數據不是很大， 可以一個個插入到樹狀數組中， 每插入一個數， 統計比他小的數的個數，對應的逆序為 i- getsum( data[i] ),其中 i 為當前已經插入的數的個數， getsum( data[i] ）為比 data[i] 小的數的個數i- sum( data[i] ) 即比 data[i] 大的個數， 即逆序的個數但如果數據比較大，就必須采用離散化方法。一關鍵字的離散化方法：所謂離散化也就是建立一個一對一的映射。
因為求逆序時只須要求數據的相應
大小關系不變。如： 10 30 20 40 50 與 1 3 2 4 5 的逆序數是相同的定義一個結構體 struct Node{ int data; // 對應數據 int pos; // 數據的輸入順序 };
先對 data 升序排序， 排序後，pos 值對應於排序前 data 在數組中的位置。再定義一個數組 p[N]， 這個數組為原數組的映射。以下語句將按大小關系把原數組與 1到 N 建立一一映射。
題目鏈接：click here
預備函數
定義一個Lowbit函數，返回參數轉為二進制後,最後一個1的位置所代表的數值.
例如,Lowbit(34)的返回值將是2；而Lowbit(12)返回4；Lowbit(8)返回8。
將34轉為二進制,為0010 0010,這裡的"最後一個1"指的是從2^0位往前數,見到的第一個1,也就是2^1位上的1.
程序上，((Not I)+1) And I表明了最後一位1的值,
仍然以34為例,Not 0010 0010的結果是 1101 1101(221),加一後為 1101 1110(222), 把 0010 0010與1101 1110作AND,得0000 0010(2).
Lowbit的一個簡便求法:（C++）
int lowbit(int x)
{
return x&(-x);
}
新建
定義一個數組 BIT，用以維護A的前綴和，則:
具體能用以下方式實現：（C++）
void build()
{
for (int i=1;i<=MAX_N;i++)
{
BIT[i]=A[i];
for (int j=i-1; j>i-lowbit(i);j-=lowbit(j))
BIT[i]+=BIT[j];
}
}
修改
假設現在要將A[I]的值增加delta,
那麼,需要將BTI[I]覆蓋的區間包含A[I]的值都加上K.
這個過程可以寫成遞歸,或者普通的循環.
需要計算的次數與數據規模N的二進制位數有關,即這部分的時間復雜度是O(LogN)
修改函數的C++寫法
void edit(int i, int delta)
{
for (int j = i; j <= MAX_N; j += lowbit(j))
BIT[j] += delta;
}
求和
首先,將ans初始化為0，將i計為k.將ans的值加上BIT[P]將i的值減去lowbit(i)重復步驟2～3，直到i的值變為0
求和函數的C/C++寫法
int sum (int k)
{
int ans = 0;
for (int i = k; i > 0; i -= lowbit(i))
ans += BIT[i];
return ans;
}
復雜度
初始化復雜度最優為O(N)
單次詢問復雜度O(LOG(N))其中N為數組大小
單次修改復雜度O(LONG(N))其中N為數組大小
空間復雜度O(N);
代碼：
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1000001;
const double eps=1e-6;
const double pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
struct node
{
int data,pos;
} doo[maxn];
int n;
int coo[maxn],poo[maxn];
int cmp(const void *a,const void *b)
{
node *ta=(node *)a;
node *tb=(node*)b;
return ta->data-tb->data;
}
int cmp1(node aa,node bb)
{
return aa.data-bb.data;
}
void updata(int pos,int value)
{
int x=pos;
while(x<=n)
{
coo[x]+=value;
x+=lowbit(x);
}
}
int getsum(int pos)
{
int x=pos,sum=0;
while(x)
{
sum+=coo[x];
x-=lowbit(x);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&doo[i].data);
doo[i].pos=i;
}
qsort(doo+1,n,sizeof(doo[0]),cmp);
// sort(doo,doo+n,cmp1);
int id=1;
poo[doo[1].pos]=1;
for(int i=2; i<=n; i++)
if(doo[i].data==doo[i-1].data) poo[doo[i].pos]=id;
else poo[doo[i].pos]=++id;
memset(coo,0,sizeof(coo));
long long ans=0;
for(int i=1; i<=n; i++)
{
updata(poo[i],1);
ans+=(long long )(i-getsum(poo[i]));
}
printf("%lld\n",ans);
// int n,s=0;; //暴力
// int a[100];
// scanf("%d",&n);
// for(int i=0; i
歸並排序合並算法
#include
#include
#define MAXM 1000003
#define INF 0x7fffffff-1;
long long cnt;
int arr[MAXM];
int temp1[MAXM/2+1], temp2[MAXM/2+1];
void Merge(int array[], int start, int mid, int end)// 歸並排序中的合並算法
{
int n1, n2,i,k,j;
n1 = mid - start + 1;
n2 = end - mid;
for (i = 0; i < n1; i++) // 拷貝前半部分數組
{
temp1[i] = array[start + i];
}
for ( i = 0; i < n2; i++) // 拷貝後半部分數組
{
temp2[i] = array[mid + i + 1];
}
temp1[n1] = temp2[n2] = INF; // 把後面的元素設置的很大
for ( k = start, i = 0, j = 0; k <= end; k++)// 逐個掃描兩部分數組然後放到相應的位置去
{
if (temp1[i] <= temp2[j])
{
array[k] = temp1[i];
i++;
}
else
{
cnt+=n1-i; //逆序對的個數
array[k] = temp2[j];
j++;
}
}
}
// 歸並排序
void MergeSort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
// 對前半部分進行排序
MergeSort(array, start, i);
// 對後半部分進行排序
MergeSort(array, i + 1, end);
// 合並前後兩部分
Merge(array, start, i, end);
}
}
int main()
{
//freopen("11.txt","r",stdin);
//freopen("2.txt","w",stdout);
int T,i,n;
scanf("%d",&T);
while(T--)
{
cnt=0;
scanf("%d",&n);
for(i=0; i
