Блог пользователя failed_coder

Автор failed_coder, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just maintain a polynomial of degree 3 on every node.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.