Efficient Solutions to Variants of Inversion Problems of Range Minimum Queries
The 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM2026),
Lecture Notes in Computer Science Vol.16448, pp.16-30
(2026), [peer-reviewed]
Event Date:
February 9-13, 2026
Abstract / 概要
Given a set of results from range minimum queries (RMQs), our task is to construct a sequence that is consistent with the results of the queries. We study two types of RMQs: a value-based RMQ returns the minimum value and an index-based RMQ returns the index of the minimum. While the value-based version has been discussed informally in the context of competitive programming, the index-based version appears to be unexplored. In this paper, we provide a survey and unified analysis of the value-based version, and we propose efficient algorithms for the index-based version. These include algorithms for computing the lexicographically smallest consistent sequence and permutation, as well as an enumeration algorithm that outputs all consistent permutations with constant delay.