归并排序（注意long long）

#include<cstdio>
using namespace std;
int data[1000003];
int fu[1000003];
long long res = 0;
void qsort(int l, int r)
{
    if(l == r) return;
    int mid = l + (r - l) / 2;
    qsort(l, mid);
    qsort(mid + 1, r);
    int p1 = l, p2 = mid + 1;
    int p3 = l;
    while(p1 <= mid || p2 <= r)
    {
        if(p1 <= mid && p2 <= r)
        {
            if(data[p1] <= data[p2]) fu[p3++] = data[p1++];
            else 
            {
                res += (mid - p1 + 1);
                fu[p3++] = data[p2++];
            }
        }
        else if(p1 <= mid && p2 > r) fu[p3++] = data[p1++];
        else fu[p3++] = data[p2++];
    }
    for(int i = l; i <= r; i++)
    data[i] = fu[i]; 
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &data[i]);
    qsort(1, n);
    printf("%lld", res);
    return 0;
}

好像多了一个数据。。。不应该是 3 1 4 5 2么。。

树状数组
（说好的正整数呢，数据里好像有Ai==0的情况）

#include<cstdio>

#ifdef WIN32
#   define outl "%I64d"
#else
#   define outl "%lld"
#endif

using namespace std;

typedef long long LL;
const int MAXN = 1000005;
int n, a[MAXN], c[MAXN];
LL ans;

int low_bit(int x){
    return x & -x;
}

void insert(int x){
    while(x < 1000000){
        c[x]++;
        x += low_bit(x);
    }
}

LL query(int x){
    LL res = 0;
    while(x){
        res += c[x];
        x -= low_bit(x);
    }
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = n; i >= 1; i--){
        ans += query(a[i]);
        insert(a[i]+1);
    }
    printf(outl, ans);
    return 0;
}

树状数组
测试数据 #0: Accepted, time = 875 ms, mem = 20376 KiB, score = 20
测试数据 #1: Accepted, time = 78 ms, mem = 20380 KiB, score = 10
测试数据 #2: Accepted, time = 500 ms, mem = 20380 KiB, score = 10
测试数据 #3: Accepted, time = 125 ms, mem = 20380 KiB, score = 10
测试数据 #4: Accepted, time = 593 ms, mem = 20380 KiB, score = 20
测试数据 #5: Accepted, time = 62 ms, mem = 20376 KiB, score = 10
测试数据 #6: Accepted, time = 359 ms, mem = 20380 KiB, score = 20
Accepted, time = 2592 ms, mem = 20380 KiB, score = 100
代码
var n,i,m,q:longint; ans:Int64;
a:array [1..4,0..1000000] of longint;
p:array [0..1000000] of longint;

procedure put(x:longint);
var i:longint;
begin
i:=1;
while a[1,i]<>0 do
if x>=a[1,i] then
begin
if a[3,i]=0 then
begin
a[3,i]:=p[m];
inc(m);
end;
inc(a[4,i]);
i:=a[3,i];
end
else
begin
if a[2,i]=0 then
begin
a[2,i]:=p[m];
inc(m);
end;
ans:=ans+a[4,i]+1;
i:=a[2,i];
end;
a[1,i]:=x;
end;

begin
read(n);
read(a[1,1]);
for i:=2 to n do
p[i]:=i;
m:=2;
for i:=2 to n do
begin
read(q);
put(q);
end;
write(ans);
end.

U43题解：
pascal
var
i,n:longint;
ans:qword;
a,b:array[0..1000001]of longint;
procedure msort(l,r:longint);
var
i,j,k,mid:longint;
begin
if l>=r then exit;
mid:=(l+r) div 2;
msort(l,mid);
msort(mid+1,r);
i:=l; j:=mid+1; k:=l;
while (i<=mid)or(j<=r) do begin//数还没有插完
if (i<=mid) and ((j>r)or(a[i]<=a[j])) then begin//插第i个数
b[k]:=a[i];
inc(i);
ans:=ans+j-mid-1;//逆序对个数
end
else begin
b[k]:=a[j];
inc(j);
end;
inc(k);
end;
for i:=l to r do a[i]:=b[i];
end;
begin
read(n);
for i:=1 to n do read(a[i]);
ans:=0;
msort(1,n);
write(ans);
end.


树状数组的童鞋不要忘了插入0的情况...

晕死，要用%I64d，树状数组卡时卡得厉害，连memset都要省略掉。注意数据里ai有相同的，没考虑会坑死！

擦咧，%lld输出long long居然出错？改成cout就AC了……

只会Mergesort哈哈

友情提示：用sbt有两个点超时

编译通过...

├ 测试数据 01：答案正确... 961ms

├ 测试数据 02：答案正确... 25ms

├ 测试数据 03：答案正确... 555ms

├ 测试数据 04：答案正确... 118ms

├ 测试数据 05：答案正确... 649ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 493ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2801ms

答案最后是Int64范围内的

数据是否带0有待考证

我的时间好慢啊...写次了...

树状数组

……水题还要交3次……

1st：数组开成了100000的（比题目少个0）

2nd：答案用成了longint（it ought to be int64）

3rd：finall AC……

树状数组轻松解决…………

太无耻了。题目明明说Ai是正整数啊~数据里偏偏带0

害我白交2次

编译通过...

├ 测试数据 01：答案正确... 400ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 275ms

├ 测试数据 04：答案正确... 9ms

├ 测试数据 05：答案正确... 275ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1078ms

越来越喜欢用指针了。。。。

因为在自己机器上调试的时候将ans设成longint,忘了改成int64，竟然害我莫名其妙的挂了三次，不仅浪费了时间，还有我宝贵的AC率。。。。！！！！

经典的merge_sort！！

program ll;

type

atype=array[1..1000000] of longint;

var

i,n,k:longint;

a,b:atype;

function sorting(lo,hi:longint):qword;

var

mid,i,j:longint;

c:qword;

begin

c:=0;

if lo

int64啊

编译通过...

├ 测试数据 01：答案正确... 774ms

├ 测试数据 02：答案正确... 25ms

├ 测试数据 03：答案正确... 399ms

├ 测试数据 04：答案正确... 87ms

├ 测试数据 05：答案正确... 602ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 352ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2239ms

米有秒杀！

sunny 是弱蛋啊弱蛋~~~

编译通过...

├ 测试数据 01：答案正确... 369ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 150ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 244ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：897ms

orz..

我爱 merge sort..

编译通过...

├ 测试数据 01：答案正确... 338ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 166ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 259ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 119ms

orz

我爱puppy。。。。。