PROBLEM LINK:
Author: Trung Nguyen
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
sqrt-decomposition, bit operations
PROBLEM:
There are n monsters, i^{th} of them initially has h_i health points. You need to process q queries of the kind: given x,y, subtract y hp from all monsters which index is submask of x, i.e. k ~\&~x=k . After each query calculate number of living monsters.
QUICK EXPLANATION:
Break queries into blocks of \sqrt q queries and after each block calculate total hp loss for each enemy. When some enemy is killed, go through all queries in block to find out which query killed it.
EXPLANATION:
Let’s break queries into \sqrt q blocks. Once you read entire block, recalculate hp of each enemy. You can do it by following function:
template<typename T>
void sum_overmasks(T l, T r) {
if(r - l == 1) {
return;
}
T m = l + (r - l) / 2;
sum_overmasks(l, m);
sum_overmasks(m, r);
int n = m - l;
for(int i = 0; i < n; i++) {
l[i] += l[i + n];
}
}
This function takes iterators l and r to the begin and the end of subarray (i.e. semi-interval [l;r)). After this if r-l is the power of two and we consider that subarray is indexed in such way that element under iterator l has index 0 then after this function works out, it will calculate for each index i sum of elements in array such that i is submask of their indices.
Indeed two recursive calls will process it correctly for halves of array. After that i and i+n will correspond to same submask except for largest bit which will be set to 0 in i and to 1 in i+n thus arr_i + arr_{i+n} will cover all overmasks of i.
That is, given overall damage for each mask in query, you will calculate damage to each enemy. Now if some enemy got killed at particular block, you can go through all queries in this block and find particular query at which enemy got killed. That will solve the problem. Overall complexity is O(q+n \sqrt q).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.