A problem idea

Here is one problem idea that I have. I do have a slight feeling that this might be a very standard or direct question. Please give feed back or suggestions to improve the question.

Here is the basic statement.

Given an array of 10^5 positive numbers ( each no. <= 10^5 ). and 10^5 queries of the form M L R.
aL%M + a(L+1)%M … aR%M.

Hey Sundar,

What I felt is that, this problem is too standard, and also I remember(vaguely), Ajay and me discussing some problem from some OJ which involved this as a sub-problem (I could search for where it occurred problem if you need).

Also, I’m not sure if this exact problem has already occurred somewhere.

We could keep this as a substitute problem though, or even develop on this and make it difficult. What do you think ?

^agreed, its standard. ( -_- editing the wrong suggestion)

@Anmol Ya… I also agree that it might be standard. We can keep this is for worst case as substitute i guess. If possible give me the link of that problem. It would help in modifying this question.

@ mohit Can you explain how to do without segment trees? . I could not think of anyway without using segment trees.

@sundar is it just not (sum[r] - sum[l-1]) % M. Where sum[i] = sum{a[0]…a[i]}

@anudeep no. For a = 100 150 200 300 and query = 150 1 4 answer is 100+ 0+ 50+ 0 = 150


I had a Nsqrt(N)logN solution mind, which works for M <= 10^5.
It basically, is for M < sqrt(N), initially store mod of every element, and then later just do a range sum.
For M >= sqrt(N), do queries in form [0,M-1],[M,2M-1]…
For [Mi,M(i+1)-1] query, if count is c and sum is s, add sum - c(M*i) and so on…
And we’ll compute all queries offline.

I discussed different approaches to solve this problem with sundar then,
Sundar has a similar but less complex approach he said.

But now I feel, we should keep this in the problem set. What do you guys think ?

Also, does someone have a different approach maybe, or can we make this problem more tuff.

The best solution I have is O( N * sqrt( N * log N ) ). It is very similar to what is described above, just a different block size. I have one solution that is offline and another that is online. So you could as well add an update operation (change A[i] to X) if you want to make contestants avoid offline solution.

Even I had this block size in mind.Can you explain your online solution? I could not think of one. Also I think(not sure) we can add update a[i] = x and still do it offline by rebuilding the segment tree and calculating answers for queries whenever no. of queries added reaches N or no. of updates reaches sqrt(N).

I’d like to be the tester for this question.

@Sundar, could you give me the input format, and the exact constraints. Also, in the meantime, could you also start preparing the statement and the test-data.

Input format.

1 st line contains no. of test cases T.

For each test case

1st line contains an integer N <= 10^4

Next line contains N integers representing the array A.

3rd line contains M the no. of queries ( <= 10^4)

Next M lines contain queries. each are either of the form

1 L R MOD( find answer from L to R with modulo MOD)

2 i val ( set a[i] = val )

1 <= L <= R <= N

1 <= i <= N

1 <= val <= N.

T <= 20