SRM649div1med:XorSequence

時間間に合うように実装したつもりだけどなんか時間かかってる・・・(最悪1.919sとかだった)なんでこんな時間かかるのかよくわからない(多分mapかなとは思っている)ので誰か教えて欲しいです。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13249&rd=16313

解法:div2hardと発想は同じ。ただ今回は配列Aのサイズが結構大きいのでそこは注意が必要。そこでどうするかというと、上からk番目のbitが同じもの同士でグループ分けしてそのそれぞれについて上からk+1番目のBのbitを0にするか1にするかを決定していけば良い。
以下ソースコード

ll getReverse(const vector<int>& a) {
    ll sum = 0;
    ll ans = 0;
    int n = a.size();
    for (int i = 0; i < n; i++) {
        if (a[i] > 0) ans += sum;
        else sum++;
    }
    return ans;
}

class XorSequence {
public:
    ll getmax(int N, int sz, int A0, int A1, int P, int Q, int R) {
        vector<ll> A(sz);
        A[0] = A0; A[1] = A1;
        for (int i = 2; i < sz; i++) {
            A[i] = (A[i-2]*P + A[i-1]*Q + R) % N;
        }
        int K = __builtin_popcount(N-1);
        ll ret = 0;
        for (int k = K; k >= 1; k--) {
            vector<ll> cmp(2);
            map<ll, vector<int> > m;
            for (int i = 0; i < sz; i++) {
                m[(A[i]>>k)].push_back((A[i]>>(k-1))&1);
            }
            for (auto el : m) {
                vector<int> p = el.second;
                cmp[0] += getReverse(p);
                for (int i = 0; i < (int)p.size(); i++) p[i] ^= 1;
                cmp[1] += getReverse(p);
            }
            ret += max(cmp[0], cmp[1]);
        }
        return ret;
    }
};