Original link: https://www.shuizilong.com/house/archives/hdu-3303-harmony-forever/
Title meaning
For the set S, there are two operations: 1, BX; 2, AY. BX means adding X to the set S, and assigning X a serial number, which represents the number it is; AY means finding the smallest number mod Y from the set S, and outputting the number of the number.
practice
A very powerful question.
Discuss y in blocks, the small y is violently updated every time it is added, and the large y is converted into an rmq problem.
(I think this is the difficulty of this question. For the modulo operation, it is difficult for me to think about rmq, which seems to be more complicated.)
Note that this rmq can be offline, and for static problems, it can be monotonically stacked (refer to the previous O(n)-O(1) RMQ), and only the addition operation can become a set split, and vice versa It becomes and checks.
This article is transferred from: https://www.shuizilong.com/house/archives/hdu-3303-harmony-forever/
This site is only for collection, and the copyright belongs to the original author.