# Editorial for CCC '17 S5: RMT

Before reading the editorial, please make sure you've read the problem thoroughly multiple times and tried your best to solve it. Thanks!

Proceed to Editorial

Proceed to Editorial

^{1/2}. Each will store the sum of that block. First, note that when we operate a line, most trains will stay inside each block. Only 1 train will leave, and 1 train will enter each block. As such, we can update all the sums in O(N

^{1/2}). For each block we store the first and last element of each line. When we perform a survey, if a block is contained in the range to be queried, we add it's pre-stored sum. Otherwise, we iterate over the elements that reside in the query range. This operation also takes O(N

^{1/2}). Time Complexity: O(QN

^{1/2}) Space Complexity: O(MN

^{1/2})