Find the number of unique elements on segment online

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	Radewoosh	3415
8	Um_nik	3376
9	maroonrk	3361
10	XVIII	3345

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	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, Treap_to_Find> POSITIONS;
    for (int i = 0; i < n; i++) {
        POSITIONS[a[i]].Add(i);
    }
    for (int i = 0; i < n; i++) {
        if (POSITIONS[a[i]].Find(-1) == false) {
            POSITIONS[a[i]].Add(-1);
        }
        if (POSITIONS[a[i]].Find(n) == false) {
            POSITIONS[a[i]].Add(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]].Del(pos);
            POSITIONS[val].Add(pos);
 
            if (POSITIONS[val].Find(-1) == false) {
                POSITIONS[val].Add(-1);
            }
            if (POSITIONS[val].Find(n) == false) {
                POSITIONS[val].Add(n);
            }
 
            int Last_for_val = POSITIONS[val].Find_ll(pos);
            int Future_for_val = POSITIONS[val].Find_rr(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 - POSITIONS[val].Find_ll(pos);
            future[pos] = POSITIONS[val].Find_rr(pos);
 
            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.

Comments (7)

Show archived | Write comment?

re-wa-tl-ok

14 months ago, hide # |

Auto comment: topic has been updated by re-wa-tl-ok (previous revision, new revision, compare).

→ Reply

M1chael_Petrov

Auto comment: topic has been updated by M1chael_Petrov (previous revision, new revision, compare).

arvindf232

+24

this problem is exactly identical to 2D point update, 2D range sum query, as the transformation gives. In the first case, no point update necessary.

There are three optoins for the first case, wavelet tree, merge sort tree, or persistent segment tree. All of which are n log n, but wavelet tree allow bit-compression so it is actually n log n / 64 in memory, n log n time, which is the best solutoin.

The second case is a general unavoidable full on 2D queries, costing n log^2 n. but you can still choose between 2D BIT (if range small), red-black tree on segment tree, and 2d segment tree. If all queries are given ahead of time (offline) you can change the red-black tree on segment tree into BIT on segment tree after coordinate compression, which would be clearley the best option. If one of the range is dense (which is applicable here), use red-black tree on segment tree.

I think the solution to this problem is best presented by clearly splitting to a "reduction" component and an "data structure" component, I hope the examples I give show you why such a split is desirable.

i_love_sqrt_decomp

13 months ago, hide # |

← Rev. 2 →

There's yet another way: use sqrt decomposition online. $$$O(n\sqrt{n}\log(n))$$$. My idea is that when an element changes, you should change the left link too. Then use a similar idea as a merge sort tree, i.e. maintain a sorted list of elements in each block. It runs quite fast and beats all MO 3D implementations that I know. The problem (in Vietnamese): https://lqdoj.edu.vn/problem/diffquery2, my solution: https://gist.github.com/pt13762104/7a29af08b17fbffb87ca35e0ffcc0e88. Also I don't think you need the right link when you already have the left link.

13 months ago, hide # ^ |

Your nickname is very suitable for this way of solving the problem) Yes, I submitted a similar solution last year.

"Also I don't think you need the right link when you already have the left link." — It depends on what problem you're solving. To find the number of different elements, it is enough to store one link; and to find unique, you need 2, because both will have to go out of range. ([1, 2, 3, 3] has 2 unique elements: 1 and 2). Both tasks have their pros and cons in implementation.

As I understand it, here you are talking about different elements. Perhaps I really should have defined the "unique elements" at the beginning of the blog. Then there would be no misunderstandings.

I think this is a clearer solution.

Murasame-chan

We can still use Mo's algorithm for online queries. Maybe you think this is unbelievable, but this is really possible.

See this tutorial (In Chinese, but you can copy Markdown src here and do AI translation). The provided code is for problem P1903, which is almost the same as Problem 2 at the start of this blog

re-wa-tl-ok's blog

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