代码如下，区别在于分治函数countInversion返回值的调用方法，理论上来讲应该是从左到右依序计算的，然而并不能通过，改写强制规定调用顺序之后AC，有点蛋疼。。。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

char s[200][100],dna[100],sortedDna[100];
int inversion[200];
int dna_index[200];

int mergeSort(int l, int m, int r) {
    int index_first = l,index_second = m;
    int index = l;
    int count = 0;
    while(index_first < m || index_second < r) {
        if(index_first >= m){
            sortedDna[index++] = dna[index_second++];
            continue;
        }
        if(index_second >= r) {
            sortedDna[index++] = dna[index_first++];
            continue;
        }
        if(dna[index_first] > dna[index_second]) {
            sortedDna[index++] = dna[index_second++];
            count += m - index_first;
        } else {
            sortedDna[index++] = dna[index_first++];
        }
    }
    for(int i = l;i < r;i ++) // Copy sorted array back
        dna[i] = sortedDna[i];
    //printf("%s,%d %d %d,count:%d\n",dna,l,m,r,count);
    return count;
}

int countInversion(int l, int r) {
    if(l + 1 >= r) return 0;
    int m = (l + r) / 2;
    int l_value = countInversion(l, m), r_value = countInversion(m, r);
    return l_value + r_value + mergeSort(l, m, r); //AC
    //return countInversion(l, m) + countInversion(m, r) + mergeSort(l, m, r); //WA
}

void swap(int a,int b) {
    int t = inversion[a];
    inversion[a] = inversion[b];
    inversion[b] = t;
    t = dna_index[a];
    dna_index[a] = dna_index[b];
    dna_index[b] = t;
}

int divide(int l, int r) {
    int pivot_value = inversion[r - 1],pivot_index = dna_index[r - 1];
    int sort_index = l - 1;
    for(int i = l;i < r - 1;i ++) {
        if(inversion[i] < pivot_value) swap(i, ++sort_index);
        else if(inversion[i] == pivot_value && dna_index[i] < pivot_index) swap(i, ++sort_index);
    }
    swap(++sort_index, r - 1);
    return sort_index;
}

void qsort(int l, int r) {
    if(l + 1 >= r) return;
    int q = divide(l, r);
    qsort(l, q);
    qsort(q + 1, r);
    return;
}

int main(int argc, const char * argv[]) {
    int n,m;
    scanf("%d %d", &m, &n);
    for(int i = 0;i < n;i ++) {
        scanf("%s",s[i]);
        memcpy(dna, s[i], sizeof(char) * 100);
        //inversion[i] = count_inver(s[i], m);
        inversion[i] = countInversion(0, m);
        dna_index[i] = i;
    }
    qsort(0, n);
    for(int i = 0;i < n;i ++)
        printf("%s\n",s[dna_index[i]]);
    return 0;
}