Hello Codeforces,

It is sometimes required in competitive programming problems to segment a range defined as [first, last) of indices in a given data container, where first refers to the first element to inspect and last refers to the element past the last element to inspect, into a number of intervals such that all the consecutive elements in any interval have the same value of a particular segmentation function $$$f(x)$$$ whose value depends on the present element $$$x$$$ only, and this value is different from the function value in the intervals before and after such interval if any of them exists.

This blog presents a simple C++ template data structure for such purpose.

The following is the declaration and implementation of the data structure.

template<class ForwardIt, class UnaryFunction>
struct seg: vector<size_t> {
    inline seg(ForwardIt first, ForwardIt last, const UnaryFunction& fun) {
        if (first != last) {
            size_t width = 1; 
            for (auto present_value = fun(*first++); first != last; ++width) {
                const auto next_value = fun(*first++);
                if (next_value != present_value)
                    push_back(width), present_value = next_value, width = 0; }
            push_back(width); } } };

The seg data structure inherits vector<size_t> as a base class to store the range-segmentation results. The data-structure constructor seg(ForwardIt first, ForwardIt last, const UnaryFunction& fun) has three parameters: first and last specify the range [first, last), and fun specifies the segmentation function.

The time-complexity of constructing an object/instance of this data structure should be $$$O((S+T+U).N)$$$, where $$$S$$$, $$$T$$$ and $$$U$$$ are the execution times required to complete the segmentation function call fun(*first), to append an element to the vector using a vector<size_t>::push_back(width) member function call, to increment the iterator first, respectively, and $$$N = last-first$$$ is the range size.

The following are sample applications of this data structure.

1. CodeChef Starter 35: Chef Find XOR Beautiful

2. Codeforces Round #784 (Div. 4): D. Colorful Stamp