PROBLEM LINK:
Author: Devendra Agarwal
Tester: Sergey Kulik
Editorialist: Lalit Kundu
DIFFICULTY:
HARD
PREREQUISITES:
Binary Indexed Trees/Segment Trees
Mathematics and Number Theory
PROBLEM:
Given fixed parameters R, p1, p2 (p1,p2 are primes) and array A, perform three operations:
* 0 S D X Y: Add an AGP with the start term of S, the common difference of D, common ratio of R from the X-th to the to Y-th element of A.
* 1 X g: A[X] = (A[X])g modulo p2.
* 2 X Y: Output (A[X] + ā¦ + A[Y]) modulo p1.
Array A can have upto 105 elements and upto 105 queries.
EXPLANATION:
We can see AGP as an infinite AGP. To add an AGP from [X,Y] is equivalent to adding 2 inļ¬nite AGPās which are:
(a) Start Term = S, Common Difference = D and Starting from X.
(b) Start Term = ā(S + (Y ā X + 1) * D) * RY-X+1, Common Difference = āD * RY-X+1 and starting from Y+1.
Now the solver can use any data structure such as BIT/segment tree. But since BIT are easy to implement and efficient, I will discuss the approach using BIT.
Supose that using BIT, we somehow solve queries 0 and 2, how can we solve query 1 efficiently. Here we keep two BIT, one is modulo p1 (say BIT1) and other modulo p2 (say BIT2). For query 1 ie. 1 X g
// read respective values at X
var1=read(BIT1,X)
var2=read(BIT2,X)
// update to make both indexes 0
update(BIT1,X,-var1)
update(BIT2,X,-var2)
// update to add new values
update(BIT1,X,var2^g mod p2)
update(BIT2,X,var2^g mod p2)
Now, we have to answer queries 0 and 2. Let us analyse the situation after just one addition of query 0 (which is added at X, as we have broken 1 AGP into 2 infinite AGpās).
Let us find sum of all elements from 1 to J.
Multiplying with R, we get
Subtracting above 2 equations, we get
Simplifying, we get
Let 
Let 
Let 
Note:
(a) BADD, T and Z are independent of query point J.
(b) 
By using Fact (a), we can store BADD, T and Z in the BIT (as it is independent of query point) in the update query 0 and use fact (b) for query of type 2.
Solution is not yet complete as we need to augment our data structure with yet another field ADD, which keeps the constant addition of the value in the index. This is used intially and for query 1. So, the output of query 2 changes from (b) to:
Ā© 
Wait, the solution is not yet over! What if (R-1)2 is not coprime to prime numbers, then we wonāt be able to find INVERSE of it and hence our solution will fail. In this case, the problem transforms to AP as R mod prime = 1 mod prime.
Solve for AP in the similar idea using data structures.
Complexity of solution is O( N * log(N) ) intially, plus O ( log(N) ) for each query. So overall complexity is O( (N+Q)* log(N)).
See setterās solution for implementation details using the above idea.
ALTERNATE SOLUTION:
(as told by @triveni)
There was no need of computing any kind of inverse modulo or such things at all to solve this problem, using the method that I followed. Even if p1 and p2 are not primes, this problem can be solved very easily using the same approach. I used Segment Tree data Structure. In my opinion, the hardest part to solve this problem is to find the sum of the AGP in efficiently. It is said in the editorial, we need to compute Modulo((R-1)**2).
But actually we can do something better here.
sum(i) = S + (S+D)*R + (S+2D)*R^2 + (S+3D)*R^3 +ā¦+ (S+(i-1)*D)*R^(i-1)
=>sum(i) = (S + SR + SR^2 + SR^3 + SR^4 +ā¦) + (0 + DR + 2DR^2 + 3DR^3 + 4DR^4 +ā¦)
=>sum(i) = S(1 + R + R^2 + R^3 + R^4 +ā¦) + D(0 + R + 2R^2 + 3R^3 + 4R^4 +ā¦)
=>sum(i) = S * X(i) + D * Y(i)
Now, what one can do is pretty simple. Just pre-compute the value of X(i) and Y(i) for all 1<=i<=N.
Hence, it becomes pretty easy. Here is my solution using segment tree approach http://www.codechef.com/viewsolution/3844832.
This method doesnāt assume anything about primeness of p1 and p2.