I am thinking of a programming problem about segment tree .. Here is the statement :
An array of N ( N < 10^5) integers is given. I have 2 type of total M (10^5) operation on the array
1. U a b d v // Means Update value of index a , a+d, a+2d , a + 3d ..... <=b by value v ( add the value of v to those index )
2. Q a b d // Meaning sum of arr[a] , arr[a+d] , arr[a+2d] , ..... until b
O based index system
Here is an example :
Input :
6 5 // N M
0 1 2 3 4 5 // The array
U 1 5 2 2
Q 1 2 1
Q 1 5 3
Output :
5
7
The Time limit is standard (3s) How to solve it Efficiently ????
I guess you can solve it with sqrt-decomposition and this problem looks very tricky for tree-like structures. Not the exact solutions follows, just my thoughts: queries with large steps (d) can be performed straightforwardly (because such query affects no more than
elements), and queries with small steps can be grouped by size of step.
yeputons, can you please explain me in details how to do the "queries with small steps can be grouped by size of step"? I just can think in a segment tree for each r and d such that d <= sqrt(n) and r = a (mod d).
Thank you.
Yep, exactly this thing. It will take
memory.
-1
Hi, could you kindly paste the link to the problem? :)
As I mentioned , This problem is thought,not found.. I just learning segment tree & think how to update this kind of operation.. yeputons Methods seems to run in reasonable time .. This may be an accepted solution Though sort(n) is 20 times bigger than log N for N = 10^5 , for strict time limit , it could fail...