Optimization of counting the amounts of cyclic array elements

The task is clearly olympiadna but oh well.

The general idea is a segment tree with lazy operations and maintaining a balance of vertices. For simplicity, we fix the value in MOD. This will not complicate the task much, but it will be easier to debug.

Yes, there are a lot of multiplications by 2, you can replace x+x x<<1 and so on as you like.

The main link is http://e-maxx.ru/algo/segment_tree

Element structure

 struct Node{ long sum; int CountV[MOD]; int pending; } 

We will need support functions:

 void AddMod(int CountV[MOD], int delt){ //выполняет сдвиг массива int temp[MOD]; //(можно оптимальнее) memcpy(temp,CountV,MOD*sizeof(int)); for (int i=0;i<MOD;i++) CountV[(i + delt) % MOD] = temp[i]; } void addV(int &x, int y){ //добавляет число по модулю x+=y; x%=MOD; } void relax(int U, int d){ //добавляет в вершине отложенно d AddMod(U, d); addV(Tree[U].pending, d); Tree[U].sum = 0; for (int i = 0;i<10;i++) Tree[U].sum += i*Tree[U].CountV[i]; } void forcePush(int U){ //"пропихивает" через вершину отложенное relax(2*U,Tree[U].pending); relax(2*U + 1,Tree[U].pending); Tree[U].pending = 0; Tree[U].sum = 0; for (int i = 0;i<10;i++) Tree[U].sum += i*(Tree[U].CountV[i] = Tree[2 * U].CountV[i] + Tree[2 * U + 1].CountV[i]); } 

Further we do a standard tree a root in 1 !:

 void add(int U, int L, int R, int l, int r, int val) { //l,r - нужный if (L >= r || R <= l) return; //отрезок l = max(l, L); r = min(R, r); if (L == l && R == r) { relax(U,val); return; } forcePush(U); add(2 * U, L, (L + R) >> 1, l, r, val); add(2 * U + 1, (L + R) >> 1, R, l, r, val); forcePush(U); } long getSum(int U, int L, int R, int l, int r) { if (L >= r || R <= l) return 0; l = max(l, L); r = min(R, r); if (L == l && R == r) return Tree[U].sum; forcePush(U); long res = getSum(2 * U, L, (L + R) >> 1, l, r) + getSum(2 * U + 1, (L + R) >> 1, R, l, r); return res; } void init(int U, int L, int R){ if (L >= R) return; if (L + 1 == R){ Tree[U].CountV[ INIT[L] ] = 1; Tree[U].sum = INIT[L]; return; } init(2*U,L, (L + R) >> 1); init(2*U+1,(L + R) >> 1,R); for (int i = 0;i<10;i++) Tree[U].sum += i*(Tree[U].CountV[i] = Tree[2 * U].CountV[i] + Tree[2 * U + 1].CountV[i]); } 

Once again, the idea is that at the top of the tree there is a value how much was pushed there before. When it is necessary to count the sum, we simply stretch these values, when we go down, we push this value. Then everything seems to be simple, I recommend to read this tree completely.

Calls - getSum(1,0,MaxN, left, rigth);

At the request of more.

At each vertex we know the number of elements equal to i in its segment.

Imagine that the add request will be exactly the segment covered by the vertex. Then we put a mark at the top of what's added there and that's it. If the coverage is not complete, then there is no choice, go left and right, we do until it completely coincides. If there was something at the top and we were going to go down, then we immediately push the value down (you can shove with the sum, there is no difference, just debugging is easier).

Now the amount. If we come to a vertex that contains exactly the required segment, then we can easily calculate the sum in it from the array. (the sum of i*Count[i] ). If not, go down and push through the value. Now that we have reached such a vertex, we need to perform a deferred summation. To do this, simply call the AddMod function described above. I think it is not necessary to explain what she does.

Full build code http://ideone.com/1vuNAm .

Here you can optimize (for example, 2 calls forcePush(U); add not needed). But I will leave it as an exercise :)