Find the number of unique elements on segment online

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	142
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Problem 1:

Problem 2:

Of course, offline, both tasks can be solved using Mo algorithm and 3DMo (there are many ways like scanline, etc.), but there are some problems where we need to answer queries online. The solution with a persistent segment tree, i heard from Andrew-13, is good, but it does not support update queries. So, let's get started and learn how to solve both problems.

Problem 1: $$$O(log(n)^2)$$$ on query using 2D Implicit Segment Tree

What is a "unique" element in a subarray? — an element in a subarray $$$a[ l, r ]$$$ is considered unique if it appears exactly once in that range => it's previous occurrence (if any) is before $$$l$$$ and it's next occurrence (if any) is after $$$r$$$.

Let's introduce the definition: link of $$$a_i$$$ is a reference that points to an equal element that is located closer to the left/right than others. If there are no such links, the left link leads to $$$-1$$$, and the right link leads to $$$n$$$.

Now we need to find the number of elements on $$$[ l, r ]$$$ such that their left links point to elements at positions < $$$l$$$, and the right links to elements at positions > $$$r$$$. So, let's build $$$future$$$ and $$$last$$$ — arrays containing links to the closest equal elements:

$$$future_i$$$ contains the index of the closest element equal to $$$a_i$$$ on the right (or $$$n$$$ if there are no such elements).
$$$last_i$$$ contains the index of the closest element equal to $$$a_i$$$ on the left (or $$$-1$$$ if there are no such elements).

We will consider current query: $$$[ l, r ]$$$. Let's just count elements with $$$future_i$$$ > $$$r$$$ and $$$last_i$$$ < $$$l$$$ => — $$$last_i$$$ > — $$$l$$$ => $$$1000000$$$ — $$$last_i$$$ > $$$1000000$$$ — $$$l$$$. Now all coordinates are positive, because $$$l$$$, $$$last_i$$$ < $$$n$$$ < $$$10^5$$$.

So, we need to count the number of points ($$$x_i$$$, $$$y_i$$$) = ($$$1000000$$$ — $$$last_i$$$, $$$future_i$$$) which lie in the upper right part of plane relative to ($$$minX$$$, $$$minY$$$) = ($$$1000000$$$ — $$$l$$$, $$$r$$$). 2D Implicit Segment Tree can easily solve this problem in $$$O(log(n)^2)$$$.

This would be a solution if there were no points:

lies before the left border and the right link crosses the right border.
lies after the right border and the left link crosses the left border.

So, we get the number of unnecessary points and subtract it from the total answer. This can be realized with simple Segment Tree with Treaps in nodes, because we actually need to be able to answer to 2 queries:

count the number of elements on [ $$$0$$$, $$$l$$$ — $$$1$$$ ] that have right links > $$$r$$$.
count the number of elements on [ $$$r$$$ + $$$1$$$, $$$n$$$ — $$$1$$$ ] that have left links < $$$l$$$.

Finally: Precalc ~ $$$O(n * log(n)^2)$$$; Answer to query ~ $$$O(log(n)^2)$$$.

Code

void Solve() {
    int n; cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> base(n);
    for (int i = 0; i < n; i++) {
        base[i] = 0;
    }

    SegmentTree LAST(base);

    map<int, int> last_id;
    for (int i = 0; i < n; i++) {
        last_id[a[i]] = -1;
    }

    vector<int> last(n);
    for (int i = 0; i < n; i++) {
        LAST.update(i, 0, last_id[a[i]]);

        last[i] = 1'000'000 - last_id[a[i]];
        last_id[a[i]] = i;
    }

    SegmentTree FUTURE(base);

    map<int, int> future_id;
    for (int i = 0; i < n; i++) {
        future_id[a[i]] = n;
    }

    vector<int> future(n);
    for (int i = n - 1; i >= 0; i--) {
        FUTURE.update(i, 0, future_id[a[i]]);

        future[i] = future_id[a[i]];
        future_id[a[i]] = i;
    }

    vector<int> X;
    for (int i = 0; i < n; i++) {
        X.push_back(last[i]);
    }

    vector<int> Y;
    for (int i = 0; i < n; i++) {
        Y.push_back(future[i]);
    }

    vector<pair<int, int>> points;
    for (int i = 0; i < n; i++) {
        points.push_back({ X[i], Y[i] });
    }

    SegmentTree2D ST;
    for (auto p : points) {
        ST.update(p.first, p.second, 1);
    }

    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;

        --l;
        --r;

        int min_X = 1'000'000 - l;
        int min_Y = r;

        cout << ST.query(min_X + 1, min_Y + 1, inf, inf) - LAST.query_L(r + 1, n - 1, l - 1) - FUTURE.query_R(0, l - 1, r + 1) << endl;
    }
}

Problem 2: $$$O(log(n)^2)$$$ on query using 2D Implicit Segment Tree

What about update queries? Note that we can also easily answer them in $$$O(log(n)^2)$$$. Let's call $$$L$$$ — the maximum position in $$$a$$$ that < $$$i$$$ and $$$a_L$$$ = $$$X$$$; $$$F$$$ — the minimum position in $$$a$$$ that > $$$i$$$ and $$$a_F$$$ = $$$X$$$, where $$$X$$$ is the element in the update query. If there are no such elements, just put: $$$L$$$ = $$$-1$$$; $$$F$$$ = $$$n$$$.

When updating an element $$$a_i$$$, the links only change:

$$$a[i]$$$ links.
$$$a[last_i]$$$ links.
$$$a[future_i]$$$ links.
$$$a[L]$$$ links.
$$$a[F]$$$ links.

It remains to remember to update Segment Tree of Treaps and the points on the 2D Segment Tree plane.

Finally: Precalc ~ $$$O(n * log(n)^2)$$$; Answer to query ~ $$$O(log(n)^2)$$$.

Code

void Solve() {
    int n; cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> base(n);
    for (int i = 0; i < n; i++) {
        base[i] = 0;
    }

    SegmentTree LAST(base);

    map<int, int> last_id;
    for (int i = 0; i < n; i++) {
        last_id[a[i]] = -1;
    }

    vector<int> last(n);
    for (int i = 0; i < n; i++) {
        LAST.update(i, 0, last_id[a[i]]);

        last[i] = 1'000'000 - last_id[a[i]];
        last_id[a[i]] = i;
    }

    SegmentTree FUTURE(base);

    map<int, int> future_id;
    for (int i = 0; i < n; i++) {
        future_id[a[i]] = n;
    }

    vector<int> future(n);
    for (int i = n - 1; i >= 0; i--) {
        FUTURE.update(i, 0, future_id[a[i]]);

        future[i] = future_id[a[i]];
        future_id[a[i]] = i;
    }

    vector<int> X;
    for (int i = 0; i < n; i++) {
        X.push_back(last[i]);
    }

    vector<int> Y;
    for (int i = 0; i < n; i++) {
        Y.push_back(future[i]);
    }

    vector<pair<int, int>> points;
    for (int i = 0; i < n; i++) {
        points.push_back({ X[i], Y[i] });
    }

    SegmentTree2D ST;
    for (auto p : points) {
        ST.update(p.first, p.second, 1);
    }

    map<int, set<int>> POSITIONS;
    for (int i = 0; i < n; i++) {
        POSITIONS[a[i]].insert(i);
    }
    for (int i = 0; i < n; i++) {
        if (POSITIONS[a[i]].find(-1) == POSITIONS[a[i]].end()) {
            POSITIONS[a[i]].insert(-1);
        }
        if (POSITIONS[a[i]].find(n) == POSITIONS[a[i]].end()) {
            POSITIONS[a[i]].insert(n);
        }
    }

    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        string Type; cin >> Type;

        if (Type == "!") {
            int pos, val; cin >> pos >> val;

            --pos;

            if (a[pos] == val) {
                continue;
            }

            if (future[pos] != n) {
                LAST.update(future[pos], pos, 1'000'000 - last[pos]);
                ST.update(last[future[pos]], future[future[pos]], -1);
            }
            if (1'000'000 - last[pos] != -1) {
                FUTURE.update(1'000'000 - last[pos], pos, future[pos]);
                ST.update(last[1'000'000 - last[pos]], future[1'000'000 - last[pos]], -1);
            }

            if (future[pos] != n) {
                last[future[pos]] = last[pos];
                ST.update(last[future[pos]], future[future[pos]], 1);
            }
            if (1'000'000 - last[pos] != -1) {
                future[1'000'000 - last[pos]] = future[pos];
                ST.update(last[1'000'000 - last[pos]], future[1'000'000 - last[pos]], 1);
            }

            ST.update(last[pos], future[pos], -1);

            POSITIONS[a[pos]].erase(pos);
            POSITIONS[val].insert(pos);

            if (POSITIONS[val].find(-1) == POSITIONS[val].end()) {
                POSITIONS[val].insert(-1);
            }
            if (POSITIONS[val].find(n) == POSITIONS[val].end()) {
                POSITIONS[val].insert(n);
            }

            int Last_for_val = *(--POSITIONS[val].lower_bound(pos));
            int Future_for_val = *POSITIONS[val].upper_bound(pos);

            LAST.update(pos, 1'000'000 - last[pos], Last_for_val);
            FUTURE.update(pos, future[pos], Future_for_val);

            last[pos] = 1'000'000 - Last_for_val;
            future[pos] = Future_for_val;

            a[pos] = val;

            ST.update(last[pos], future[pos], 1);

            if (Future_for_val != n) {
                LAST.update(Future_for_val, Last_for_val, pos);
                ST.update(last[Future_for_val], future[Future_for_val], -1);
            }
            if (Last_for_val != -1) {
                FUTURE.update(Last_for_val, Future_for_val, pos);
                ST.update(last[Last_for_val], future[Last_for_val], -1);
            }

            if (Future_for_val != n) {
                last[Future_for_val] = 1'000'000 - pos;
                ST.update(last[Future_for_val], future[Future_for_val], 1);
            }
            if (Last_for_val != -1) {
                future[Last_for_val] = pos;
                ST.update(last[Last_for_val], future[Last_for_val], 1);
            }
        }
        else {
            int l, r; cin >> l >> r;

            --l;
            --r;

            int min_X = 1'000'000 - l;
            int min_Y = r;

            cout << ST.query(min_X + 1, min_Y + 1, inf, inf) - LAST.query_L(r + 1, n - 1, l - 1) - FUTURE.query_R(0, l - 1, r + 1) << endl;
        }
    }
}

You can find my solution here.

Rev.	By	When	Δ	Comment
ru14	re-wa-tl-ok	2025-04-04 20:42:29	9	Мелкая правка: '\n\n<spoiler' -> '\n<spoiler'
en7	re-wa-tl-ok	2025-04-04 15:19:10	299
ru13	re-wa-tl-ok	2025-04-04 15:17:34	300
ru12	re-wa-tl-ok	2025-03-26 23:16:20	7	Мелкая правка: '\n<spoiler s' -> '<spoiler s'
ru11	M1chael_Petrov	2025-03-26 22:42:54	92	Мелкая правка: '\n\n<spoiler' -> '\n<spoiler'
ru10	M1chael_Petrov	2025-03-26 22:39:41	34
ru9	M1chael_Petrov	2025-03-26 22:31:52	8237
en6	M1chael_Petrov	2025-03-26 22:10:35	0	Tiny change: '\n\n<spoiler' -> '\n<spoiler'
ru8	re-wa-tl-ok	2025-03-26 22:09:38	0	Мелкая правка: '\n\n<spoiler' -> '\n<spoiler'
en5	re-wa-tl-ok	2025-03-26 22:06:41	0	Tiny change: '\n\n<spoiler' -> '\n<spoiler'
en4	re-wa-tl-ok	2025-03-26 22:01:12	0	Tiny change: '\n\n<spoiler' -> '\n<spoiler'
en3	re-wa-tl-ok	2025-03-26 21:55:20	1	Tiny change: '\n\n<spoiler' -> '\n<spoiler'
en2	re-wa-tl-ok	2025-03-26 21:49:50	1	Tiny change: '\n\n<spoiler' -> '\n<spoiler' (published)
en1	re-wa-tl-ok	2025-03-26 21:41:17	10622	Initial revision for English translation (saved to drafts)
ru7	re-wa-tl-ok	2025-03-26 21:26:11	0	Мелкая правка: '\n\n<spoiler' -> '\n<spoiler' (опубликовано)
ru6	re-wa-tl-ok	2025-03-26 21:25:25	2
ru5	re-wa-tl-ok	2025-03-26 21:23:32	13	Мелкая правка: '\n<spoiler s' -> '<spoiler s'
ru4	re-wa-tl-ok	2025-03-26 21:17:58	81	Мелкая правка: 'imgur.com/a/7ILXcP6)\n\nSo, w' -> 'imgur.com/bNIHfu7)\n\nSo, w'
ru3	re-wa-tl-ok	2025-03-26 20:36:46	0	Мелкая правка: '\n\n<spoiler s' -> '<spoiler s'
ru2	re-wa-tl-ok	2025-03-26 20:04:22	96
ru1	re-wa-tl-ok	2025-03-26 19:54:04	10466	Первая редакция (сохранено в черновиках)

Problem 1: $$$O(log(n)^2)$$$ on query using 2D Implicit Segment Tree

Problem 2: $$$O(log(n)^2)$$$ on query using 2D Implicit Segment Tree

History