I have solved it using just segment trees and lazy propagation. Actually combining two different approaches:
If number of updates is high use segment tree with lazy propagation where each node contains:
a) Max value in interval
b) Index of this max value
c) delayed add value
Combine function is trivial.
Now when querying - start query 100 steps to the right from start (or last query point) , then from
maxindex -1, and again… forming the sequence or just counting , then continue again 100 steps away. if returns value below the current max - break out as there is a gap of 100, if found Kth - return it
Different segment tree if the number of updates is less frequent then queries - in this case index tree is “almost” a merge tree , node value contains vector of pairs (val,index) containing strongly increasing sequence.
plus “add” value for lazy propagation of the updates.
When merging (combining) - just find lower bound of the right end of the left segment in the right vector and merge right part of the right vector to the left vector. (Take care about “add” values of both parts as they shift whole vector up or down)
Plenty of optimisation is possible and this potentially could even work for high update number. But combination of these two solutions in one - solves the problem with 100 points.
solution link: Link to the AC Solution