信息学奥赛一本通：1311：【例2.5】求逆序对

给定一个序列a1,a2,…,an，如果存在iaj，那么我们称之为逆序对，求逆序对的数目。

第一行为n,表示序列长度，接下来的n行，第i+1i行表示序列中的第i个数。

所有逆序对总数。

N≤105，Ai≤105。

用归并排序，来计算

#include
using namespace std;
long long sum=0;
int N;
#define MAX 100010
int D[MAX];
int tmp[MAX]; 
void merge(int a[],int s,int m,int e)
{
	int pb=0,p1,p2;
	p1=s;
	p2=m+1;
	while(p1<=m&&p2<=e){
		if(a[p1]>a[p2]){//找到逆序，它后面的都是
			sum+=(m-p1+1);
			tmp[pb++]=a[p2++];
		}
		else
		tmp[pb++]=a[p1++];
		}
		while(p1<=m){
	 tmp[pb++]=a[p1++];}
		while(p2<=e)
		tmp[pb++]=a[p2++];
	for(int i=0;i>N;
	for(i=0;i>D[i];
			
		mergesort(D,0,N-1);
		cout< 
 
第二个：
 
 
//  It's not my program
//  ????? 
#include 
#include 
using namespace std;
int tree[500005];
int A[500005],B[500005];
int n;
int cnt = 1;
//?????? 
int read() {
char ch = getchar();
int num = 0;
bool fl = 0;
for(; !isdigit(ch); ch = getchar())
if (ch=='-') fl = 1;
for(; isdigit(ch); ch = getchar())
num = (num<<1)+(num<<3)+ch-48;
if(fl) num = -num;
return num;
}
int lowbit(int k)
{
return k&(-k);
}
void updata(int k,int num)
{
  while(k<=cnt)
  {
  tree[k]+=num;
  k+=lowbit(k);
  }
} 
int getsum(int k)
{
int ans = 0;
while(k)
{
ans+=tree[k];
k-=lowbit(k);
}
return ans;
}
int getnum(int t,int ri)
{
int le = 1;
int mid=(le+ri)/2;
while(let)
{
ri = mid-1;
mid=(le+ri)/2;
}
else
{
le=mid+1;
mid=(le+ri)/2;
}
}
}
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{   
A[i] =read();
B[i] = A[i];
}
//?????
sort(B+1,B+n+1);
tree[1] = 0;
for(int i =2;i<=n;i++)
{
if(B[i]!=B[i-1]) 
{
B[++cnt] = B[i];
tree[cnt] = 0;
}
}
int t;
long long sum = 0;
for(int i = 1;i<=n;i++)
{
int t =getnum(A[i],cnt);
//cout<