school competition 1 [技術室奥プログラミングコンテスト#4 Day1 I]

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i

解説

https://atcoder.jp/contests/tkppc4-1/submissions/6665112

全探索対象を探そう。
なんとなく、PQRSとなっているので、Pで全探索できないか考える。
Pの位置の人が決まればどうなるかを考えると、Rの位置の人として採用できる組み合わせが何通りかが決まる。
しかも、Rとして何を採用してもQ,Sの選択には影響を及ぼさない。
これは使えそう。
なので、lft[p] := レーティングがpの人を採用した時、Rの位置の人として採用できる人の組み合わせ
これに右側の組み合わせをかければ、Pの位置にその人が来た時の組み合わせは網羅できる。

右側の組み合わせを考えると、Qの位置にある人が来たときにSの位置にくることのできる人が決まる。
これを事前計算しておく。
rht[q] := レーティングがqの人を採用した時、Sの位置の人として採用できる人の組み合わせ
Pの位置にその人が来た時にQの位置に来ることのできる人全員のrhtの組み合わせを足すことで右側の組み合わせが得られる。

ちょっと説明がわかりにくいが、実装としては、A,Bはまずソートする。
lft[p], rht[q]を計算する。
Pを全探索しながら、rht[q]の総和を使って、答えを計算していく。
座標圧縮を使うと実装が少し楽。

int N, M, A[201010], B[201010];
int cntA[401010];
BIT<int> cntB(401010);
BIT<mint> lft(401010), rht(401010);
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) cin >> B[i];

    // compression
    vector<int> dict;
    rep(i, 0, N) dict.push_back(A[i]);
    rep(i, 0, M) dict.push_back(B[i]);
    sort(all(dict));
    dict.erase(unique(all(dict)), dict.end());
    rep(i, 0, N) A[i] = lower_bound(all(dict), A[i]) - dict.begin();
    rep(i, 0, M) B[i] = lower_bound(all(dict), B[i]) - dict.begin();

    rep(i, 0, N) cntA[A[i]]++;
    rep(i, 0, M) cntB.add(B[i], 1);

    rep(i, 0, 401010) rht.add(i, cntB.get(i + 1, 401010) * cntA[i]);

    mint ans = 0;
    rep(p, 0, 401010 - 10) {
        mint lf = cntB.get(0, p);
        mint rh = rht.get(p + 1, 401010);
        ans += lf * rh * cntA[p];
    }
    cout << ans << endl;
}