I tried to solve this problem and spend alot of time and all I got O(N*log^2N) solution (segment tree) which got TLE on it Polynomial Queries
simply the problem is about increase range (a, b) the 1st element by 1, 2nd by 2, and so on like arithmetic sequence and answering queries online
any help would be appreciated :-)
You can solve it with a lazy segment tree and maintaining two lazy values per segment. Suppose we have a query of type 1 over a segment [a, b]. Suppose now we arrived in the segment tree at some segment [c, d] that is in the range [a, b] (c >= a && d <= b). Now we should add $$$(c - a + 1) + (c - a + 2) + (c - a + 3) + ... + (d - a + 1)$$$ to the segment sum of [c, d]. This is the same as adding $$$(c - a) * (d - c + 1) + 1 + 2 + 3 + ... + (d - c + 1)$$$ to the segment sum of [c, d]. Because we make use of lazy propagation we add the values to the lazy nodes: lazy1[idx] adds $$$c - a$$$ and lazy2[idx] is increased by one (the total times you should add $$$1 + 2 + 3 + ... + (d - c + 1)$$$ to this segment so far. So you can solve it in $$$O(Q log N)$$$.
can i see the code? i tried but idk how to handle the pushing down
Or you could be more exotic and solve it with Fenwick Tree instead.
Here's the idea: when you add a value, say $$$x$$$, to a segment $$$[lo,\ hi]$$$, the first element is incremented by $$$x$$$, the second by $$$x + 1$$$, and so on, till the last element of the segment is incremented by $$$x + (hi - lo)$$$. Only, in this question $$$x = 1$$$. We'll see what happens to the prefix sum post an update:
Post update, in the prefix sum, the elements in the range $$$[1,\ lo)$$$ stays constant. The element in the range $$$[lo,\ hi]$$$, with an index $$$idx$$$, is incremented by $$$(idx\ -\ lo)\ *\ x\ +\ [(idx\ -\ lo)\ *\ (idx\ -\ lo\ +\ 1)]\ /\ 2$$$. And the elements in the range $$$(hi,\ N)$$$ are incremented by $$$(hi\ -\ lo\ +\ 1)\ *\ x\ +\ [(hi\ -\ lo)\ *\ (hi\ -\ lo\ +\ 1)]\ /\ 2$$$. Similar to how multiple Fenwick trees can be used to handle range updates and range queries, we can use 6 BITs here for the update. The first will take care of $$$idx$$$. The second will take care of constant terms. The third will take care of doubled $$$idx^{2}$$$. The fourth will take care of doubled $$$idx$$$. The fifth will take care of doubled constant terms. And the sixth will hold the initial prefix sum (prior to any update(s)). Notice that I've taken doubled terms because I'm splitting the terms which are being divided by $$$2$$$ so it's possible that it no longer stays divisible by $$$2$$$. Consequently, all doubled terms are halved at queries to nullify the effect. Here's the implementation, for the writing might be confusing without something concrete:
There is another way to solve that problem, you can use SQRT decomposition on queries.
The main idea is, you split all $$$Q$$$ queries into $$$\sqrt{Q}$$$ blocks, each block has $$$\sqrt{Q}$$$ queries.
In each block, there are some update queries and range queries. In each block, when you read an update query, you save it into a temporary vector, and when you read a range query, you iterate through all pending queries in your temporary vector, and add to your answer, based on how that update query affect your current range (intersect, outside, or inside).
After processing each block completely, you have to update the whole array, so your array will be ready for the next blocks of query.
This solution doesn't need any advanced data structures like Fenwick Tree or Segment Tree, just an array of prefix sum is enough.
About the complexity, you may have some observation:
In each block, the complexity to solve each block is at most $$$Q_u \times Q_r$$$, i.e the number of update queries times the number of range queries. Because of AM-GM inequality, it will not exceed $$$\dfrac{Q}{4}$$$.
And after each block, you have to update the whole array in $$$O(N)$$$.
Then, the final complexity is $$$O((N + Q) \sqrt{Q})$$$, which is enough for the problem constraint.
You can see my code for more detail : https://hastebin.com/ogerunavit.cpp
I think you have a mistake in calculating the complexity. Because $$$ab \leq \frac{(a+b)^{2}}{4}$$$, the time complexity should be $$$Q_{u} * Q_{r} \leq \frac{Q^2}{4}$$$ which is time limited exceeded.
The bound of $$$Q_u$$$ and $$$Q_r$$$ is consider in each block of queries, not the whole $$$Q$$$ queries, so the bound of them in each block is $$$\dfrac{\sqrt{Q}}{2}$$$. And we have $$$\sqrt{Q}$$$ blocks.
You can try to submit my code, it runs in under 1 second on CSES.
I tried to explain my approach here.
Hope it helps.
Plus in the second part I have coded the solution, just in case anyone needs spoon-feeding :).