I hit ABC last night, so I'm just posting today.
T1 Starfleet (USSR)
The Borůvka algorithm can be used directly, and of course the prim algorithm can be optimized with a line tree, but I haven't played it just yet.spouting gibberish: is to maintain the current connectivity block, but when a point $ i $ joins the connectivity block, those points behind can have $ a_j - a_i $ contributions, and the points in front can have $ a_i - a_j $ contributions, and then the interval is modified, and at the same time, one can no longer be selected, and a single point modifies itself to inf , and then the global query can be made.
A $ o(n) $ practice was invented during the QED races, which proved to be correct, and will not, RUN.
T2 Peaceful Elite
Sai Shi can think of enumeration by value domain, is $ O(qn^2) $, because from the value domain to go to enumerate the last two of the answer is $ v $ words, $ \gt v $ can only be given to &, $ \lt v $ can only be given to |, $ = v $ need to be divided into a discussion: if more than two then each side of the one, if there is only one then to each side of the two to see which one can be.
And then one of the $ n $ is because we want to enumerate to find the sum of those numbers &, and the sum of |, but that can be optimized directly to $ log(n) $ using a line tree, so there's $ O(qnlog(n)) $ for that.
The reason we enumerate value fields is because they satisfy the property that the smaller the value, the smaller the value, and the larger the value, the larger the value. In fact, this property is also satisfied in the popcount, so we directly enumerate the popcount is v, but this time $ = v $ case is a bit of a problem, because I'm not sure what his value is, but you find that if their values are different, no matter to whom they are given the final value must not be the same, so after the same judgment to continue to the above can be divided into discussions. There's also the fact that both parties must be occupied, which is also a bit of a pain in the ass, but it's just a matter of a bit more detail. Time Complexity $ o(nlog^2(n)) $
T3 Chorus of Swingers
Every two neighboring numbers will be merged into a number after one operation, then let the number after the merger is the fa of the original two numbers, and then finally must be merged into a number, for the last number we until his answer, and then we tree on the DP on the line.
If we know everything about $ fa $ at this point, how do we know the answer to $ x $?
Assume for a moment that $ y = 1 $
If $ x $ = 1/0 no matter what $ fa $ is chosen, then the probability that the different choices of $ x $ result in different final answers is added to the probability that the final answer is different if $ fa $ is 1/0 $ \times $ y = 1. Otherwise the probability that $ fa $ is different is added to the probability that $ \times $ y = 1.
Then ditto for the other cases, we just need to maintain $ ans_0 $ to denote the probability that the answer is different when $ x $ is 0, $ ans_1 $ to denote the probability that the answer is different when $ x $ is 1, and $ ans_2 $ to denote the probability that the answer is different when $ x $ is different (which is also the last requested answer), and then count the probability that a number is 0/1 from the bottom to the top, and then count the answers from the top to the bottom DP.
T4 symmetrical traveler
The explanation of this problem is actually quite clear, so the explanation of the problem is the main focus:
Problem solving:
Consider seeking travelers first\(i\) The desired position of the\(f_i\)Then the answer is\(f_i * 2^{m K}\)。
When travelers\(i\) When traveling, due to the linearity of the expectation of the\(f_i \longleftarrow \frac{1}{2}\left(2 f_{i-1}-f_i+2 f_{i+1}-f_i\right)=f_{i-1}+f_{i+1}-f_i\), considering its geometrical implications, is found to be a way of putting\(f_i\) with respect to\(f_{i-1}\) cap (a poem)\(f_{i+1}\) is symmetric with respect to its midpoint, if we set\(g_i=f_{i+1}-f_i\)Well, then jump number one.\(i\) A piece is equivalent to exchanging\(g_{i-1}\) cap (a poem)\(g_i\)。
Thus a round of travel corresponds to a\(1 \sim n-1\) The permutations of the substitutions can be found by a method similar to the fast powers of the\(K\) post-wheeling\(\left\{g_i\right\}\)And again, note that\(f_1\) is always the same, the desired positions of all the pieces can be found with a time complexity of\(O(n \log K)\)。
[==============]
First of all the position of $ x $ with respect to $ y $ after symmetry can be written as $ y*2-x $ , so the first equation is well understood, and then there is the geometric meaning of the latter, which we see as $ f_{i-1} + f_{i+1} $ as $ \frac{ f_{i-1} + f_{i+1} }{2} \times 2 $ , so this is the same as the symmetric one, and then you can see that The solution says about the symmetry of the midpoints of $ f_{i-1} $ and $ f_{i+1} $ .
And then the perceptual understanding that that $ g $ is positive, so $ g_i $ denotes the distance between $ i $ and $ i+1 $, so $ i $ is exchanging the distance between the two when it's symmetric about the midpoints of $ i-1 , i+1 $, and then the perceptual understanding that $ g $ is negative also holds.
So it becomes a substitution ring, and a fast power can be used to find the final $ g $ array, and then we know from the data range that $ f_1 $ is unchanged, so we can figure out the final $ f $ array, and then $ ans_i = f_i \times 2^{km} $.