Note that the type of each Bytelandian is completely determined by the number of Byteknights in the island. Because there are between 0 and N Bytelandians, the number of solutions is actually only between 0 and N (modulo 1000000007 :P).
Firstly, we have to determine the number of Byteknights. Let knight[n] be the number of Bytelandian that satisfies a _ i <= n <= b _ i; that is, the number of Bytelandians that said it is possible to have n Byteknights in the island. It is easy to see that the number of Byteknights can be n iff knight[n] = n.
So, we need a data structure that can perform these operations efficiently:
- Increase the values of knight[a _ i]…knight[b _ i], for each Bytelandian i by 1
- Query the value of knight[i], for each 0 <= i <= N
Because all queries are needed only after the updates, the so-called ‘partial difference’ data structure suffices. Let diff[i] be knight[i]-knight[i-1]. Operation 1 can be simulated by increasing diff[a _ i] and decreasing diff[b _ i + 1]. Operation 2 is simply the sum of diff…diff[i], which can be precalculated after the updates take place.
Secondly, we have to determine the lexicographically smallest solution. If it is possible for a Bytelandian to be a Byteknaves, then we should assign it Byteknaves, otherwise the solution would not be lexicographically smallest because ‘1’ is greater than ‘0’. A Bytelandian i can be assigned Byteknave iff there is n is a possible number of Byteknights (valid solution) and n is not in range a _ i…b _ i, i.e., he is lying.
A segment tree will perform the step efficiently. Let tree[n] = 1 if knight[n] = n, or 0 otherwise. Then we can query the number of valid solutions in a range in logarithmic time. After we decide that Bytelandian i is a Byteknave, we set all elements of the tree in the range a _ i…b _ i to zero. If it is not possible for Bytelandian i to be a Byteknave, because the number of valid solutions in the range a _ i … b _ i is the same of the number of valid solutions in the range 0…N, we must assign it a Byteknight.
Can be found here.
Can be found here.