For 2 of the 15 available marks, we can implement a solution that is ~\mathcal O((N+M)Q)~. This can be done by explicitly maintaining the number of passengers at every station. When a survey happens, we can loop over the desired stations and sum the passenger counts at those stations. To operate a line, we can manually shift over all the passengers on a line one slot as necessary.

For 4 of the available marks, we need to leverage the constraint that ~L_i \le L_{i+1}~. This constraint means that every line is a contiguous subarray on ~A~. Because the array is a contiguous subarray, instead of maintaining the explicit count of passengers at every station, we can just maintain a pointer to the first station in the line and move that by one every time a line is operated, making operating a line run in ~\mathcal O(1)~. We also need to optimize surveys down to ~\mathcal O(1)~. Two steps are required here - firstly we compute the total number of passengers in a line, prefix sums on the passenger counts over all lines, and prefix sums on the passenger counts within every line. A survey will entirely contain a contiguous portion of some of the lines, so we can use the first set of prefix sums to compute the passengers that are entirely contained with the survey. There can be at most two lines with a partial count of passengers in the survey - the first line inside the segment and the last line, and we can use the second set of prefix sums to compute the counts.

The next two subtasks that are each worth 3 additional marks - each ask to optimize one of the two possible operations that can be performed over general structures of lines.

In the first one, we have that ~M \le 200~. This means that we need operating a line to be fast, and computing surveys can be slower. To do this, we use the same track in the second subtask to maintain a pointer to the index in ~A~ which maps to the passenger count of the first station on that line, for each line. We also compute prefix sums over the passenger counts within every line. When we run a line, we shift the pointer, which runs in ~\mathcal O(1)~. When we run a survey, for every line we can binary search for the stations which are contained within the survey, and then use the prefix sums along with the pointer to compute the exact passenger counts within that line. This makes surveys run in ~\mathcal O(M \log N)~.

In the second one, we have that a line will have at most 200 trains. This means that operating a line can be slow, but computing surveys must be faster. If we maintain a binary indexed tree on ~A~, an update can be done by simulating the operating of a line directly which is ~\mathcal O(200 \log N)~. A survey is then two query operations on the binary indexed tree, which is ~\mathcal O(\log N)~.

The intended solution combines observations from both the above subtasks. Instead of maintaining a binary indexed tree, we will instead break ~A~ into subarrays of size ~\sqrt{N}~ and explicitly store the sums of all the elements in these subarrays. For each line, we will also store exactly which of these subarrays each station falls into, and specifically for each of these subarrays we'll maintain the first and last station within each subarray. We'll also compute prefix sums on the prefix counts.

When we perform a survey, we iterate over each of these subarrays. If a subarray falls entirely within the survey range, we add the count of that subarray to the survey result. Otherwise, we loop over just the elements of that subarray that fall in the survey range and explicitly add the count for each of those stations to the count. There are at most two buckets that have a partial overlap with the survey range, for ~\mathcal O(\sqrt N)~ elements to manually iterate over. There are ~\mathcal O(\sqrt N)~ buckets that can be completely contained within the survey range, so this means that a survey can be answered in ~\mathcal O(\sqrt N)~.

It remains to be able to handle running a line efficiently. When a line is run, each of the endpoints for a given subarray is shifted by 1. The sums for each subarray also need to be adjusted, but those are just increments and decrements off of the endpoints. There are ~\mathcal O(\sqrt N)~ subarrays that can be affected, so this process also runs in ~\mathcal O(\sqrt N)~.

Due to the complexity of implementation here, it is possible to only get 10/15 marks. There are a few things that can be done to improve the performance of the algorithm - for example, although the subarray size is ~\mathcal O(\sqrt N)~ for the complexity analysis, in practice it helps to make the subarray size smaller than ~\sqrt N~ because looping over subarrays that are completely contained has a low constant factor, but looping over one subarray for just the elements has a higher constant factor.