Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

failed_coder's blog

By failed_coder, history, 6 weeks ago, In English,

https://codeforces.com/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

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just maintain a polynomial of degree 3 on every node.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Hey, I was the organizer of the contest. You may try your solution here.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

$$$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.

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.