Subtask 1
There are several greedy solutions that work. We will describe two of them.
Approach 1
First, greedily form as many pairs of equal-length sticks as possible. We then loop through these pairs in descending order, completing a triangle using the largest base possible at each step. If we run out of unpaired sticks, then try breaking apart the smallest paired sticks in order to form two new bases.
Time Complexity: 
Approach 2
Binary search on the answer. To check if it is possible to make at least
triangles, note that we should take the
largest pairs of equal sticks and after that, the
smallest remaining sticks. Then, we can sort these sticks in increasing order and form triangles one by one in order, checking that the triangle inequality holds at each step.
Time Complexity: 
Subtask 2
Note that simulating the subtask 1 solutions do a lot of repeated work on equal-length sticks. With some math, it is possible to handle groups of equal-length sticks at the same time, improving the complexity from
to
.
Time Complexity:
or 
Subtask 3
We will start with the binary search greedy solution from subtasks 1 and 2. Note that the answer can change by at most
per update. The main idea is to maintain some data structures representing the current set of
triangles, such that updating these data structures by incrementing/decrementing
or adding/deleting a stick is efficient.
We need to maintain the set of
such that
and the set of
such that
. It might help to split both of these sets into two std::set
s, say "small" and "large", representing the sticks we used and the sticks we did not use. We also maintain a segment tree with a
at position
whenever we use an
and a
at position
whenever we use an
. This way, we can check whether a configuration of triangles is possible by querying whether the prefix minimum is
.
For each event, we first delete all sticks involved in the event from all the data structures, possibly decrementing our answer
in the process. Then, we repeatedly attempt to increment
by
, moving sticks between the "small" and "large" sets and using the segment tree to check whether this is possible.
Two observations greatly simplify the implementation in this subtask. One observation is that if we have extra pairs of equal-length sticks after using all the single sticks, say
pairs, then it is always possible to form
more triangles with them, which is the maximum possible. This way, we never have to consider explicitly "breaking" apart a pair of equal-length sticks. Another observation is that we do not need to ensure "small" and "large" store precisely the smallest/largest sticks after a deletion, and instead just start from the smallest/largest unused sticks whenever we attempt to increase the answer. The correctness of this can be proved similar to the original greedy algorithm.
Time Complexity: 
Subtask 4
The observation from subtask 3 that the answer changes by at most
per update still holds. Now, we need to represent the sets more efficiently by grouping equal-length sticks into one entry, similar to the optimization from subtask 1 to subtask 2. The rest of the details are the same as in subtask 3.
Time Complexity: 
Subtask 5
We will need a slightly different approach now that updates can significantly change the answer. The observation that extra pairs of equal-length sticks can always be completely used after using all the odd sticks is essential to the solution we will present.
Let
be a list of all the indices
with odd
in increasing order. Note that if
of these sticks get used, it suffices to use the
smallest ones, and we can consider doing a binary search on
. The condition we need to check is that:
Let
be the number of paired sticks that can be used with a stick of length
or smaller. Then we need
for all
, which rearranges to
for all
, i.e. the minimum
for
is at least
.
This condition is sufficient, e.g. by Hall's Marriage Theorem.
We can maintain a range minimum query, range increment lazy segment tree mapping an index
to
. To represent indices not in
, we can add a large value to those indices. Whenever we add/delete an odd stick of length
, we add
to indices
, representing shifting the index
. Whenever we add/delete some pairs of sticks of length
, we update the range
, representing a change in
. To get the answer, we can do a binary search on
and perform a segment tree query each time, taking
time in total. It is also possible to combine the binary search on
with a segment tree walk to get the answer in
time. Finally, the overall answer after each event is
, where
is the total number of pairs.
Time Complexity:
or 
Comments