extent of region We begin with the segment tree version. Note that Ershov uses a version of the segment tree where the right side of the range of responsibility is open, i.e. \([3,4)\) is equivalent to \([3,3]\) The function get below will find the size of the largest range whose prefix sum is \(k\). int get(int v, int vl, int vr, int &k) { if (k >= st[v]) { k -= st[v]; return vr - vl; } if (vl == vr - 1) { return 0; } int mid = (vl + vr) / 2; int res = get(v * 2, vl, mid, k); if (res == mid - vl) { res += get(v * 2 + 1, mid, vr, k); } return res; } It does so by allowing the \(k\) to go down to \(0\), while there are empty ranges the recursion goes to the right child, until it reaches a single element range containing an element (\(>0\)) at which point it returns \(0\).

credits It is interesting that MiFaFAOvO’s solution has the same pieces are ershov.stanislav’s solution. In fact they both use the worm method (my own naming for subsequence like states). What is interesting from MiFaFAOvO’s solution is that he uses a BIT to solve the problem. what kind of tree is a BIT While the update part of a BIT is pretty straightforward one may wonder at the reverse query part which was done in ershov’s solution \(O(\log n)\).

credit This is ershov.stanislav’s solution to the problem. summary of problem Given an array of integers (colors), find the mininum nunber of consecutive grouping containing at most \(k\) colors (number of unique integers in a subarray). greedy For a single \(k\) one can take \(O(n)\) time to greedily scan through the array and accumulate \(k\) unique integers at a time. problem size However, given the size of the problem (\(10^5\)) and the fact that we must do this for \(k \in {1,\cdots,n}\) implies that we must look for a better solution.

Segment tree Preliminaries The data structure in this segment tree information according to Antti Laaksonen in the Competitive Programmer’s Handbook comes from [62] P. Stańczyk. Algorytmika praktyczna w konkursach Informatycznych, MSc thesis, University of Warsaw, 2006. Basically the original range is stored at some offset that correspond to largest power of two that is greater or equal to the size of the range. For example a size 16 array would be stored at an offset of 16 in the array.