Codeforces Round #773 editorial

If the triangle's side is not parallel with the line , all points on this side are safe because we can intersect it with and there will be a point from which we can reach any point on this side of our triangle.

All points on the side, which is parallel with line contains are also safe if the third point has a greater :

Thus, a point can be unreachable if and only if it is the "upper" horizontal side of our triangle, because it is impossible to draw such line which would intersect with line and would not intersect with the inner part of our triangle:

It is quite easy to understand that every multiset's power is at least 1. The final answer is at east the number of distict integers in the multiset. It is possible to proof that the answer to the problem for is equal to , where is the number of distinct integers.

If the number of distinct interest is equal to , is is obvious that we can create multisets, -th multiset Will only contain integers which are equal to . We can create multisets of size 1. The answer in this case is equal to .

If the number of distinct integers is at least , we can divide the integers into groups in such way that for each all occurrences of are located in the same multiset. The answer in this case is equal to .

In the first case the answer is , in the second case — . Thus, the answer is equal to .

Let's look at the minimal integer in our multiset. Since it can be matched with only one integer, we need to create such pair. Thus, we can maintain the current multiset. We need to take the minimal element out of it (and delete it from it), find a pair for it, and delete it from the multiset if such pair exists, or add 1 to the answer if there is no such pair.

Let's prove that we can turn the array into a concatenation of tandem repeats using the operations given if and only if every letter occurs an even number of times

If there is such letter that it occurs an odd number of times there is no such sequence of operations, since the parity of the number of occurrences if letter stays the same. If we insert a different letter, the number of occurrences of letter does not change, if we insert letter , we add 2 occurrences of it. Thus, it will be impossible to split the array into tandem repeats.

If we have an array , and we want to reverse its prefix of length , we can insert a pair of letters equal to after the -th symbol, a pair of letters equal to after -th symbol and etc.

It is obvious that the first symbols of the array form a tandem repeat. We can add it to our division and cut it out from the array. The array will now have its prefix of length reversed. Thus, we can move any element to the beginning of the array, so we can simply sort it. Since every element occurs an even number of times, the resulting string will be a concatenation of tandem repeats consisting of the same letters.

If -th person is not ill, the following query exists: , such that .

Otherwise, the person's status is either unknown or they are ill.

If -th person is ill, the following query exists:, such that , and every person such that are not ill. If there is such person that they are not ill, and . In this case, it is impossible to determine if -th person is ill or not.

Let's maintain the indices of the people who might be ill using set. When we get a query , we can find the first possible ill person with an index of at least using lower_bound, after that, we need to delete this person from our set, find the next one and do the same thing until we find the first index greater than . This works in .

If a person is not in the set, he is totally healthy. Otherwise, we can use a segment tree to store such index that there is a query and store it in the -th slot of our segment tree. We can update it when we get a new query. When we understand that the -th person might be ill, we can find the first elements to the left () and to the right () of , which might be healthy using our set. The -th person is ill when the minimal element on segment is .

The solution works in .

Let's maintain a set of arrays of length , add new arrays there, delete arrays from this set and understand if the set has a suitable pair for some array. To do this, let's consider a pair of sorted arrays and of length . Let's write out all subsets of the array . Then we start a counter , and for each subset of the array we add one to , if the subset occurs in and contains an odd number of elements, and subtract one if the subset occurs in and contains an even number of elements. Note that if and have at least one element in common, then will be equal to , otherwise it will be equal to . Thus, we can maintain a trie that contains all the subsets of each array in the set. Now any request to this trie is trivially done for .

Now let's sort the arrays by and use our structure to find the first array that has a suitable pair. We can simply find the pair and maintain 2 pointers, is equal to the first array in the pair, is equal to the second array in the pair. Note that now we are only interested in pairs such that . Therefore, we will move to the left only. When we moved it once again, we will see if there is a pair for it among . If so, then we will move to the left until there is a pair for among . After that we can update the answer with . The solution works in .

It is also possible to solve this problem in using std::bitset.

First of all, calculate for each index the total sum of distances among all subsets if the closest selected position is to the left. Let , where  — the number of cpecial positions at or to the right of (if then ).

Let if position is special, otherwise .

It's not hard to see, that the value for the position in this case equals to .

Then for each calculate two values:

Since we can find first value using DNC (the second value we will find similary): we want to consider every . Then halve this segment: . Then create two polynomials:

1. The polynomial of size , where .
2. The polynomial of size , where .

By multiplying this two polinomials we can recalculate the values for positions from to and then solve two parts recursively.

Thus we can find for each index the total sum of distances among all subsets if the closest selected position is to the left. To find for each index the total sum of distances among all subsets if the closest selected positions is to the right we can do the same stuff but in inverse order.

Note, that we need to consider the case where the closest selected position to the left and the closest selected position are at the same distance from . It can be done by changing in one of the cases by the number of special positinos strickly to the right of .

It can be implemented in using FFT.