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
For 2 marks, we can execute each query explicitly.
Time Complexity: O((N + M)Q)
I will not discuss the other subtasks. They can be solved with different data structures, including PSA and BIT.
For full marks, we separate the stations into blocks of size N1/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(N1/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(N1/2).
Time Complexity: O(QN1/2)
Space Complexity: O(MN1/2)