https://codeforces.net/blog/entry/55597
Given an array of integers A1,A2,…,AN and the initial value of all elements are 0. Now you are given M queries, each belongs to one of three following types:
0 x y: Find the sum of all elements from index x to index y modulo 109+7
1 x y: Add 1×2×3 to Ax, add 2×3×4 to Ax+1, …, add (i+1)×(i+2)×(i+3) to Ax+iand so on until Ay
2 x y: Subtract 1×2×3 from Ax, subtract 2×3×4 from Ax+1, …, subtract (i+1)×(i+2)×(i+3) from Ax+i and so on until Ay
Input
The first line contains two integers N and M (1≤N,M≤10^5) — the size of the array and the number of queries, respectively.
Each of the next M lines containts three integers t x y denotes type and range of the query.
Output
For each query of type 0, print the required answer in a single line.
Sample testcase:
Input
8 4
1 1 8
0 2 8
2 4 6
0 5 6
Ouput
1974
462
Sample Clarification
In the example below:
After the first query, the array is [6,24,60,120,210,336,504,720]
The answer for the second query is 24+60+120+210+336+504+720=1974
After the third query, the array is [6,24,60,114,186,276,504,720]
The answer for the last query is 186+276=462
Just maintain a polynomial of degree 3 on every node.
I am not able to think how to do range updates in this.. I tried (n+q)✓n approach but was not able to submit it before contest ends. So even don't know whether it is right or not. https://ideone.com/1ldJlg
Hey, I was the organizer of the contest. You may try your solution here.
lets say f[i] = (i*1)*(i+2)*(i+3) you can come with bi-quadratic expression for its first j terms say S[i] = a*i^4 + b*i^3 + c*i^2 + d*i + e
now S[i] = [ a b c d e]x[ i^4 i^3 i^3 i^2 i 1 ]t
now say S[i-x] = [ A B C D E]x[ i^4 i^3 i^3 i^2 i 1 ]t = A1 X A2(t) where A = p, B = q*x, C = q*x^2, D = r*x^3, E = t*x^4
now for each update you need to update A1 vector that can be done in O(1) corresponding to a specific hi
for each query you can use prefix sum for given pair of indices and answer it O(1)
I hope this gives you a basic idea of the solution.
Thank you..
For the lazy updates just store vectors on each node holding the i's for the first node in the range when you lazy update, which when traversing down obviously the left node keeps the current first i and the right gets the first i plus the length of the first interval, and also hold whether it is positive or negative. Now to query, just update a sum on the node by traversing through all i's in the vector and using this formula here to update the sum on the range based on the length and the first i, then push them down to vectors of the child nodes. Maybe this doesn't seem like logn updates because of holding the vector of values, but I'm pretty sure the complexity still holds in amortized time as I've done this before and it worked due to only moving when it needs to, but I can't actually prove it oops. Hopefully someone can prove it or tell me I'm wrong.
Edit: Can't figure out why link is not working, never had this problem, so here it is written out: https://www.quora.com/What-is-the-sum-of-the-products-1*2*3-2*3*4-50*51*52
I guess you forgot to add the link.
Oh rip.
$$$n*(n+1)*(n+2) = n^3 + 3*n^2 + 2*n$$$, so you can solve the problem by first precalculating all prefix sums of numbers, squares and cubes, then using a segment tree with lazy propagation to perform the updates and queries.
You will need to update the starting index for updates accordingly as you move to the right in the tree and be cautious.
Also, the lazy propagation is not a sum as usual, but a queue of updates.
Here is my implementation for the above question link. In this question I have added polynomial corresponding to every query l to r For eg. for update query in l to r , I have added polynomial (x-l+1)*(x-l+2)*(x-l+3) in the range l to r and my lazy array consists of coefficients of the polynomial.
Does anyone have a link to submit a solution to this question?
EDIT: As shubhammitt pointed out above, you can submit the solution in this contest[contest:281119]. You can access the problems once you register for the contest.