## 【POJ-1007】DNA Sorting【树状数组求逆序对】

【POJ-1007】DNA Sorting【树状数组求逆序对】

Solution:

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int LIM = 30;
int bitree[LIM];

void update(int pos) {
for (; pos < LIM; pos += pos & (-pos))
bitree[pos]++;
}

int query(int pos) {
int ret = 0;
for (; pos > 0; pos -= pos & (-pos))
ret += bitree[pos];
return ret;
}

struct Node {
string str;
int cnt;
bool operator < (const Node &n) const {
return cnt < n.cnt;
}
};
vector<Node> dat;

int main(void) {
ios::sync_with_stdio(false);
// cin.tie(NULL);
int n, m;
Node tmp;
while (cin >> n >> m) {
dat.clear();
for (int i = 0; i < m; i++) {
cin >> tmp.str;
tmp.cnt = 0;
memset(bitree, 0, sizeof bitree);
for (int j = n - 1; j >= 0; j--) {
tmp.cnt += query(tmp.str[j] - 'A' + 1);
// cout << query(tmp.str[j] - 'A' + 1) << endl;
update(tmp.str[j] - 'A' + 2);
}
dat.push_back(tmp);
}
sort(dat.begin(), dat.end());
for (int i = 0; i < m; i++) {
cout << dat[i].str << '\n';
// cout << dat[i].cnt << '\n';
}
}
return 0;
}