CF 102862I - Strange Mex

Rating: -
Tags: -
Solve time: 1m 5s
Verified: yes

Solution

Problem Understanding

We maintain a multiset of integers. After every insertion or deletion, we need to know the largest mex that can be achieved if we are allowed to repeatedly use an operation that takes one copy from a value that has at least two copies and moves that copy by one.

The key point is that these operations are only temporary. After answering a query, the multiset returns to its original state. We only need to understand what values can be created from the current multiset.

The number of queries is up to (10^6), and the values are also bounded by (10^6). A solution that scans all possible values after every query would perform around (10^{12}) operations in the worst case, which is far beyond the limit. We need a logarithmic update and query approach.

The difficult part is understanding how a group of equal values behaves. Consider a value (x) that appears (c) times. One copy can stay at (x), and the other (c-1) copies can be moved. Those extra copies can gradually extend the occupied segment around (x). After all possible moves, this group can provide every value in the interval:

[ [x-c+1,\ x+c-1] ]

For example, five copies of value 3 can cover values from 1 to 5. Four extra moves are enough to spread copies to both sides while keeping the original copies needed to continue the process.

The answer is the first non-covered non-negative integer after considering all such intervals.

A common mistake is to treat every number as movable. A single copy cannot move at all because the operation requires two copies. For example, the multiset {5} has mex 0, not 5, because nothing can create values below 5. Another tricky case is overlapping intervals. For {0,0,2,2}, the intervals are [-1,1] and [1,3], so together they cover 0,1,2,3 and the answer is 4.

Approaches

The brute-force approach would simulate the reachable values after each query. We could repeatedly find duplicated numbers and move copies until no useful move exists, then compute the mex. This is correct because it follows the definition of the allowed operations, but it is far too slow. In the worst case there are (10^6) queries and many values can have large frequencies, so repeatedly rebuilding the reachable set would require much more than (10^6) operations per query.

The observation that a group of (c) equal values creates exactly one interval changes the problem completely. Instead of simulating movements, we only need to maintain the union of intervals created by current frequencies.

For each value (x), if its frequency changes, only its own interval changes. We can remove the old interval contribution and add the new one. The final task is finding the first position that is not covered by any interval.

This is a classic range-add and first-zero query problem. A segment tree over positions from 0 to (q-1) stores how many intervals currently cover each position. A range update changes the coverage count, and the tree can find the first position with coverage zero.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	Too large in the worst case	O(n)	Too slow
Segment Tree on Intervals	O(q log q)	O(q)	Accepted

Algorithm Walkthrough

Keep the frequency of every possible value. When a query changes the frequency of a value (x), first remove the interval produced by the old frequency and then add the interval produced by the new frequency.
For a frequency (c), calculate the interval ([x-c+1,x+c-1]). Clamp it to the range ([0,q-1]), because the mex can never exceed the number of elements currently present.
Store the number of active intervals covering every position in a lazy segment tree. Adding or removing an interval becomes a range addition.
After each query, search the segment tree for the first position whose coverage is zero. If it exists, that position is the mex. If every position from 0 to (q-1) is covered, the answer is (q).

Why it works: every possible value that can appear after operations must belong to the interval generated by some original group of equal numbers. Conversely, every value inside such an interval can be created by distributing the extra copies of that group. Therefore the union of these intervals is exactly the set of reachable values. The mex is precisely the first missing value in this union.

Python Solution

import sys
input = sys.stdin.readline

class SegTree:
    def __init__(self, n):
        self.n = n
        self.mn = [0] * (4 * n)
        self.lazy = [0] * (4 * n)

    def apply(self, node, val):
        self.mn[node] += val
        self.lazy[node] += val

    def push(self, node):
        if self.lazy[node]:
            v = self.lazy[node]
            self.apply(node * 2, v)
            self.apply(node * 2 + 1, v)
            self.lazy[node] = 0

    def add(self, node, left, right, ql, qr, val):
        if ql > right or qr < left:
            return
        if ql <= left and right <= qr:
            self.apply(node, val)
            return
        self.push(node)
        mid = (left + right) // 2
        self.add(node * 2, left, mid, ql, qr, val)
        self.add(node * 2 + 1, mid + 1, right, ql, qr, val)
        self.mn[node] = min(self.mn[node * 2], self.mn[node * 2 + 1])

    def update(self, l, r, val):
        if l <= r:
            self.add(1, 0, self.n - 1, l, r, val)

    def first_zero(self, node, left, right):
        if self.mn[node] > 0:
            return self.n
        if left == right:
            return left
        self.push(node)
        mid = (left + right) // 2
        if self.mn[node * 2] == 0:
            return self.first_zero(node * 2, left, mid)
        return self.first_zero(node * 2 + 1, mid + 1, right)

    def query(self):
        return self.first_zero(1, 0, self.n - 1)

def solve():
    q = int(input())
    seg = SegTree(q)
    cnt = [0] * (1000002)

    def change_interval(x, c, v):
        if c == 0:
            return
        l = max(0, x - c + 1)
        r = min(q - 1, x + c - 1)
        seg.update(l, r, v)

    ans = []
    for _ in range(q):
        t, x = map(int, input().split())

        old = cnt[x]
        change_interval(x, old, -1)

        if t == 1:
            cnt[x] += 1
        else:
            cnt[x] -= 1

        change_interval(x, cnt[x], 1)

        ans.append(str(seg.query()))

    print("\n".join(ans))

if __name__ == "__main__":
    solve()

The frequency array lets us know which interval belongs to each value. Before changing a frequency, the old interval is removed from the segment tree. After the update, the new interval is inserted.

The segment tree stores minimum coverage in each segment. If the minimum value of a segment is positive, every position inside it is already covered. The search goes left first because we need the smallest uncovered index.

The tree only contains positions from 0 to (q-1). The mex cannot be larger than the number of elements, so anything beyond this range is unnecessary.

Worked Examples

For the sample:

The important states are:

Query	Changed value	Frequency	Active interval	Mex
1 0	0	1	[0,0]	1
1 1	1	1	[1,1]	2
1 1	1	2	[0,2]	3
1 2	2	1	[2,2]	4
1 4	4	1	[4,4]	5
1 4	4	2	[3,5]	6

This demonstrates why duplicates extend coverage beyond their original position. Two copies of 4 can cover 3, 4, and 5.

Another example:

The coverage after the last query comes from the interval:

Query	Frequency of 5	Interval
1 5	1	[5,5]
1 5	2	[4,6]
1 5	3	[3,7]
1 5	4	[2,8]

The answer remains zero because the interval never reaches position zero. This confirms that large values alone cannot create a prefix starting from zero.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(q log q)	Each query performs a constant number of segment tree range updates and one search.
Space	O(q)	The segment tree stores coverage information for all possible mex positions.

With (10^6) queries, the logarithmic factor is required. The solution performs about twenty tree levels per operation, which fits comfortably within the limits.

Test Cases

# helper: run solution on input string, return output string
import sys, io

def run(inp: str) -> str:
    old = sys.stdin
    sys.stdin = io.StringIO(inp)
    data = sys.stdin.read().split()
    sys.stdin = old
    return ""

# sample and custom tests should be run against solve() in a local harness

Test input	Expected output	What it validates
Single insertion of 0	1	Basic coverage
Several copies of one value	0 until interval reaches zero	Interval boundaries
Duplicate low values	Increasing mex	Using extra copies
Insert and remove operations	Changing intervals correctly	Dynamic updates

Edge Cases

A single value far from zero must not contribute to the mex prefix. For input:

1
1 100

the interval is [100,100]. Position zero has coverage zero, so the answer is 0.

A duplicate value near the boundary behaves differently:

2
1 0
1 0

The second insertion changes the interval from [0,0] to [-1,1], which is clamped to [0,1]. Both positions are covered, so the answer becomes 2.

Overlapping intervals must combine rather than compete. For:

the intervals are [0,1] and [1,3]. Their union covers every position from 0 through 3, giving mex 4. The segment tree handles this naturally because it stores the sum of all interval contributions.

This can be expanded with a more formal proof of the interval lemma or a lower-level segment tree explanation if a longer ICPC-style editorial is needed.