ABC174 F - Range Set Query

ABC174 に出たときに、 F だけ解けずに居たので復習。

解説AC → 考察し直し → AC しました。

問題

問題文
ある数列が与えられるので、その数列の 番目から 番目までの間にある数の種類数を答えて下さいという問題。

解説AC

考察してもよく分からなかったので、まずeditorial を見ました。がよく分からず…

次に、解説動画 を見ました。 同じ数同士の距離を考えて、2次元で平面走査するというのは分かったのですが、実装できるほど腑に落ちませんでした。

そこで、もう一度考察してみました。

考察

あるクエリ を考えるときに、 から右側のうち、現れる数を数えれば良いです。

そこで、数列 を後ろから良い感じに処理していけば良さそうです（ に注目して前からでも良いです）。

数列の長さと対応した配列を用意して、 までで、各数の一番左にある数だけに 1、重複していたら 0 を入れてその和を求めることで、数が何種類あるか数えることができます。

例えば、サンプル2の

2 5 6 5 2 1 7 9 7 2

という数列を考えます。後ろから考えていくので、以下のように重複（有効）判定を更新していきます。

まず、2 は最初なので、重複は無くて数える対象ですね。

次の7,9 も同様です。

そして、次の7 では既に7 があるので先に処理した7を0 にしておきます。

このとき、 のようなクエリを処理するときは、矢印の範囲の和を取れば良いです。 の範囲には 3 種類の数がありますね。

このように、後ろから配列の更新とその場所が左端になるクエリの処理を同時にやっていくと良い感じに処理できます。 もちろん配列で の和を愚直に取ると、計算量が大きくなってしまうため、セグ木やBITなどで処理します。そうすると、 で計算できます。

何度か修正して、ソースコードとしては以下のようになりました。
最初の提出はこんな感じ

using int64 = long long;
using P = pair<int, int>;
using TP = tuple<int, int, int>;

class BIT {
    const int n;
    vector<int64> d;
public:
    BIT(int _n=0) : n(_n), d(n+1, 0) {}
    void add(int i, const int64 x=1) { for (i++; i <= n; i += i&-i) d[i] += x; }
    int64 sum(int i) { int64 x = 0; for (i++; i; i -= i&-i) x += d[i]; return x; }
};

int main() {
    int n, q;
    cin >> n >> q;

    vector c(n+1, 0);
    for (int i=1; i<=n; i++) cin >> c[i];

    vector<TP> lr;
    lr.emplace_back(-1, -1, -1);
    for (int i=1; i<=q; i++) {
        int l, r;
        cin >> l >> r;
        lr.emplace_back(l, r, i);
    }
    sort(lr.begin(), lr.end());

    unordered_map<int, int> pre;
    BIT bit(n+1);
    vector ans(q+1, -1);

    for (int i=n; i>=1; i--) {
        if (pre[c[i]] > 0) bit.add(pre[c[i]], -1);
        bit.add(i, 1);
        pre[c[i]] = i;

        while(get<0>(lr.back()) == i) {
            const auto [l, r, j] = lr.back();
            lr.pop_back();
            ans[j] = bit.sum(r);
        }
    }

    for (int i=1; i<=q; i++) cout << ans[i] << endl;
}

感想

典型らしく、Diffも水とすごく高いわけじゃなかったんですが 難しくないですか…？