Надокучливий Віслюк#12980

Надокучливий Віслюк (Розбір)

Author:

Yarema Stiahar

Solved by:

First to solve:

Infinity

Let a group be a sequence of identical characters that appear consecutively. Let’s g_i be the size of -th group. The relative order of such groups does not change, only their sizes.

To process a query of the first type, we need to find the first and the last group that will be changed by it. That process will be the same as a query of the second type. The first type of queries covers some groups entirely and at most two groups partially. Groups which are covered entirely will double in size. The group at both ends will increase in size by the number of their elements that are in range of a query. These modifications can be done with segment tree.

The second type of query has to find the smallest index such that \sum_{i = 0}^j g_i \ge x. It can be done with binary search or descent on Segment tree.

This problem can also be solved with Fenwick tree, as each group cannot double in size more than O(\log A) times. This means that we can modify each group size naively.

Complexity: O(n \log n) with descent and Segment tree or O(n \log n \log A) with Fenwick tree.