409613: GYM103643 P Reincarnation

I Couldn't Solve The USACO Bronze Problems My Teacher Gave Me, So I Got Reincarnated As A Lazy 3D Self-Balancing Persistent Segment Tree!

The new world you have been isekai'ed into has no shortage of red pandas that like to munch on apples, turnips, or potatoes. There are cows that go "moo.", and within 3366 STEps of every town square, someone is selling lunchboxes of crayons and skittles. There are happy dacs and cosy blobs living in Farmer Johns $$$10^5$$$ fields.

To get into the most prestigious school of all, "Everule Classes", you must demonstrate your capabilities.

There is an array with $$$n$$$ elements initially all set to $$$0$$$. You have to support the following two operations:

Operation of type $$$1$$$: set the values in the range $$$[l, r]$$$ to be $$$x$$$

Operation of type $$$2$$$: roll back the array to be what it was after the $$$k$$$'th update. if $$$k = 0$$$, restore the array to the initial state of all $$$0$$$'s.

After each update, you are given an integer $$$d$$$ and you have to print $$$$$$ \sum_{i = 1}^{n} a[i]^d $$$$$$ Since this value may be very large, please find it modulo $$$10^9 +7$$$.

The first line contains two integers $$$n, q$$$ $$$(1 \leq n \leq 10^6, 1\ \leq q \leq 10^5)$$$.

The next $$$q$$$ lines contain $$$q$$$ queries in the format of $$$1$$$ $$$d$$$ $$$l$$$ $$$r$$$ $$$x$$$ if it is operation $$$1$$$ or $$$2$$$ $$$d$$$ $$$k$$$ if it is operation $$$2$$$.

For all operation $$$1$$$'s: $$$(1 \leq l \leq r \leq n, 1 \leq x \leq 10^9)$$$.

For all operation $$$2$$$'s: $$$(0 \leq k < i)$$$ if it is the $$$i$$$'th query. queries are indexed starting from $$$1$$$.

For all operations $$$(1 \leq d \leq 10)$$$.

Note that all of the types of operation of the query, the interval of an operation type 1, and the version restored to of an operation type 2 are all randomly generated. The only dependent variables are $$$n$$$, $$$q$$$, the maximum value of $$$d$$$, the maximum value of $$$x$$$, and the total number of operations type 2.

If you do not trust me on this, the (poorly written) generator is linked here.

For subtasks, tests are numbered from $$$1$$$ to $$$20$$$ with the sample skipped.

Tests $$$1 - 3$$$ will have no rollback operations.

Tests $$$4 - 6$$$ will have $$$d = 1$$$ in all operations.

Output $$$q$$$ lines, the sum of $$$d$$$'th powers of the entire array.

5 5
1 2 1 3 2
1 2 3 3 1
2 1 1
1 2 4 4 1
2 1 3

12
9
6
13
6

There is initially an array of $$$[0, 0, 0, 0, 0]$$$.

After the first operation, the array becomes $$$[2, 2, 2, 0, 0]$$$ and the sum of squares is $$$2^2 + 2^2 + 2^2 + 0^2 + 0^2$$$ or $$$12$$$.

After the second operation, the array becomes $$$[2, 2, 1, 0, 0]$$$ and the sum of squares is $$$9$$$.

After the third operation, the array is restored to what it was after operation one, so it is $$$[2, 2, 2, 0, 0]$$$. $$$2^1 + 2^1 + 2^1 + 0^1 + 0^1$$$ is $$$6$$$.

After the fourth operation, the array becomes $$$[2, 2, 2, 1, 0]$$$ and the sum of squares is $$$13$$$.

After the fifth operation, the array is restored to what it was after the third operation, so it is $$$[2, 2, 2, 0, 0]$$$ and the sum of $$$6$$$.

$$$---------------------------------------------$$$

Problem idea: 3366

Problem preparation: 3366

Occurrences: Intermediate 12, Advanced 10