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: ~\mathcal{O}\left(Q(N + \sum c_i)\right)~

Approach 2

Binary search on the answer. To check if it is possible to make at least ~x~ triangles, note that we should take the ~x~ largest pairs of equal sticks and after that, the ~x~ 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: ~\mathcal{O}\left(Q(N + \sum c_i) \log \sum c_i\right)~

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 ~\mathcal{O}\left(N + \sum c_i\right)~ to ~\mathcal{O}(N)~.

Time Complexity: ~\mathcal{O}(QN)~ or ~\mathcal{O}\left(QN \log \sum c_i\right)~

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 ~1~ per update. The main idea is to maintain some data structures representing the current set of ~x~ triangles, such that updating these data structures by incrementing/decrementing ~x~ or adding/deleting a stick is efficient.

We need to maintain the set of ~\ell~ such that ~c_\ell = 1~ and the set of ~\ell~ such that ~c_\ell = 2~. It might help to split both of these sets into two std::sets, say "small" and "large", representing the sticks we used and the sticks we did not use. We also maintain a segment tree with a ~+1~ at position ~\lfloor \ell/2 \rfloor+1~ whenever we use an ~c_\ell = 1~ and a ~-1~ at position ~\ell~ whenever we use an ~c_\ell = 2~. This way, we can check whether a configuration of triangles is possible by querying whether the prefix minimum is ~\ge 0~.

For each event, we first delete all sticks involved in the event from all the data structures, possibly decrementing our answer ~x~ in the process. Then, we repeatedly attempt to increment ~x~ by ~1~, 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 ~p~ pairs, then it is always possible to form ~\lfloor 2p/3 \rfloor~ 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: ~\mathcal{O}((N+Q) \log N)~

Subtask 4

The observation from subtask 3 that the answer changes by at most ~1~ 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: ~\mathcal{O}((N+Q) \log N)~

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 ~o_1,\dots,o_m~ be a list of all the indices ~\ell~ with odd ~c_\ell~ in increasing order. Note that if ~k~ of these sticks get used, it suffices to use the ~k~ smallest ones, and we can consider doing a binary search on ~k~. The condition we need to check is that:

Let ~f(i) := \sum_{j \ge \lfloor i/2 \rfloor+1} \lfloor \frac{c_j}{2} \rfloor~ be the number of paired sticks that can be used with a stick of length ~i~ or smaller. Then we need ~f(o_i) \ge k-i+1~ for all ~1 \le i \le k~, which rearranges to ~f(o_i)+i \ge k+1~ for all ~1 \le i \le k~, i.e. the minimum ~f(o_i)+i~ for ~1 \le i \le k~ is at least ~k+1~.

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 ~o_i~ to ~f(o_i)+i~. To represent indices not in ~o_1,\dots,o_m~, we can add a large value to those indices. Whenever we add/delete an odd stick of length ~\ell~, we add ~\pm 1~ to indices ~\ell+1,\dots,N~, representing shifting the index ~i~. Whenever we add/delete some pairs of sticks of length ~\ell~, we update the range ~1,\dots,2\ell-1~, representing a change in ~f(o_i)~. To get the answer, we can do a binary search on ~k~ and perform a segment tree query each time, taking ~\mathcal{O}(\log^2 N)~ time in total. It is also possible to combine the binary search on ~k~ with a segment tree walk to get the answer in ~\mathcal{O}(\log N)~ time. Finally, the overall answer after each event is ~k + \lfloor 2(p-k)/3 \rfloor~, where ~p := \sum \lfloor \frac{c_j}{2} \rfloor~ is the total number of pairs.

Time Complexity: ~\mathcal{O}(N \log N + Q \log^2 N)~ or ~\mathcal{O}((N+Q) \log N)~