Car Show [HackerRank 101 Hack 52 C]

https://www.hackerrank.com/contests/101hack52/challenges/car-show

N個の配列がある。
Q個のクエリに答える。
「[L[i],R[i]]の連続部分列のうち、全ての数がdistinctであるものは何通りあるか」

前提知識

• Mo's Algorithm

解法

https://www.hackerrank.com/contests/101hack52/challenges/car-show/submissions/code/1304337919

Mo's Algorithmで解く。
かなり雑な説明をしているので、Mo's Algorithmを理解してから読むことを勧める。
（ちなみに想定解は遅延評価セグメントツリー）

以下、全ての数がdistinctである連続部分列をよい部分列と呼ぶ。
その前に
bak[i] := i番目の要素までの連続部分列で良い部分列である最も左の添字
nxt[i] := i番目の要素からの連続部分列で良い部分列である最も右の添字
を予め計算しておく。
以下、[i,j]の区間を扱っていると考える。

removeL(int x);
最も左の要素を消すので、全ての数がdistinctな最も右なrを探す。
r = min(nxt[x], j)
より、[x,?]な良い部分列はr-x+1通りあるので、これを答えから引く。
　
残りのremoveR,addL,addRも同様に処理していく。

typedef long long ll;
int N, Q, A[101010], L[101010], R[101010];
ll ans[101010];
int S = 765;
//---------------------------------------------------------------------------------------------------
ll sm = 0;
int bak[101010], nxt[101010];
int memo[1010101];
void init() {
    rep(i, 0, 1010101) memo[i] = 0;
    rep(i, 0, N) {
        bak[i] = memo[A[i]];
        if (i) bak[i] = max(bak[i], bak[i - 1]);
        memo[A[i]] = i + 1;
    }
    rep(i, 0, 1010101) memo[i] = N - 1;
    rrep(i, N - 1, 0) {
        nxt[i] = memo[A[i]];
        if (i < N - 1) nxt[i] = min(nxt[i], nxt[i + 1]);
        memo[A[i]] = i - 1;
    }
}
//---------------------------------------------------------------------------------------------------
int i = -1, j = -1;
void removeL(int x) {
    int r = min(j, nxt[x]);
    sm -= r - x + 1;
}
void removeR(int x) {
    int l = max(i, bak[x]);
    sm -= x - l + 1;
}

void addL(int x) {
    int r = min(j, nxt[x]);
    sm += r - x + 1;
}

void addR(int x) {
    int l = max(i, bak[x]);
    sm += x - l + 1;
}
void answer(int x) {
    ans[x] = sm;
}
//---------------------------------------------------------------------------------------------------
void mos() { // [ L[i], R[i] ] is OK, [,) is bad!!!
    init();

    vector<int> ord;
    rep(i, 0, Q) ord.push_back(i);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        if (L[a] / S != L[b] / S) return L[a] / S < L[b] / S;
        else return R[a] < R[b];
    });

    rep(_i, 0, Q) {
        int o = ord[_i];

        while (j < R[o]) { j++; if (0 <= j)addR(j); }
        while (i > L[o]) { i--; if (0 <= i) addL(i); }
        while (j > R[o]) { if (0 <= j)removeR(j); j--; }
        while (i < L[o]) { if (0 <= i) removeL(i); i++; }

        answer(o);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, Q) cin >> L[i] >> R[i];
    rep(i, 0, Q) L[i]--, R[i]--;

    mos();

    rep(i, 0, Q) printf("%lld\n", ans[i]);
}