$$$a=0$$$, $$$b=x$$$ works. Actually, $$$a$$$&$$$b+a|b$$$ is just $$$a+b$$$ :p

The only nodes with positive $$$a_u$$$ are the ancestors of the node with $$$0$$$ assigned to it. For each of them, $$$a_u$$$ can be at most its subtree size, but you can always make it exactly its subtree size. So let $$$dp_u$$$ be the answer in the subtree of $$$u$$$. $$$dp_u=max$$$ $$$dp_c+sz_u$$$, where $$$c$$$ loops over $$$u$$$'s children.

Let's forget about the updates. Let's divide the array into blocks of maximal size where every block consists of equal elements. From every block, you can only take one element, but you can always take exactly one element, so the answer is the number of blocks. Or, alternatively, it's the sum of $$$[a_i \neq a_{i-1}]$$$ plus $$$1$$$. Now in every update, only $$$2$$$ elements of this sum can change, so you can update it in $$$O(1)$$$.

For every prime, let its first multiple be at index $$$f$$$ and its last multiple at index $$$l$$$. You can't split anywhere between $$$f$$$ and $$$l-1$$$, but any other index is fine for this prime. So you have some ranges, and you want the first index that doesn't belong to any of the ranges, which is a standard problem that can be solved using cumulative arrays.

Let's see if the $$$i^{th}$$$ bit is $$$0$$$ or $$$1$$$ for every $$$i$$$. In every element, the bits more significant than the $$$i^{th}$$$ don't matter anymore, so let's throw them away. Now, let's take the sum of the elements (that is, the sum of the first $$$i$$$ bits of every element.) I claim that the $$$i^{th}$$$ bit has a $$$1$$$ if this sum is at least $$$2^i$$$. That's because if the sum is less than $$$2^i$$$, all subsequence sums are less than $$$2^i$$$, so this bit can't be $$$1$$$ in any. Otherwise, if some number has a $$$1$$$ in this bit, the answer clearly has a $$$1$$$. Otherwise, let's add the elements to the sum one-by-one. Then, by discrete continuoity, the sum can't jump from $$$0$$$ to at least $$$2^i$$$ without passing on some value that has a $$$1$$$ in the $$$i^{th}$$$ bit. You can see that this boils down to just: the answer is the or of all the elements and the prefix sums. I don't know if I like or hate this tbh.

The problem asks for the number of distinct subsequence sums of $$$[l,l+1,\ldots,r]$$$. Let's fix the number of elements, $$$x$$$. Then, you can make every single sum between (the sum of the smallest $$$x$$$ elements) and (the sum of the largest $$$x$$$ elements.) That's because if you can make the sum $$$s$$$, and $$$s$$$ isn't maximal, then there's an element $$$i$$$ such that $$$i$$$ belongs to the subsequence and $$$i+1$$$ doesn't. Remove $$$i$$$ and add $$$i+1$$$; you get a subsequence with sum $$$s+1$$$. Now, you have some ranges, and you want to see how many elements don't belong to any ranges. Let $$$f(x)$$$ be (the sum of the smallest $$$x+1$$$ elements) minus (the sum of the largest $$$x$$$ elements) minus $$$1$$$. We want the sum of the positive values of $$$f(x)$$$ between $$$0$$$ and $$$r-l$$$. If you do the algebra, you'll find $$$f(x)=x^2+(l-r)x+(l-1)$$$, a quadratic function. From now on, there's a shitty algebraic solution where you get the zeros of the function and reduce it to range sum over a quadratic function, but there's a cute solution. Try to prove that there can't be many positive values, only $$$O(\sqrt{l})$$$. That allows you to just iterate over the prefix and the suffix until you hit a negative value, and you get an insanely short and elegant code.

So we want to keep our nodes split into $$$2$$$ sets, $$$s_1$$$ and $$$s_2$$$, so that all the edges between $$$s_1$$$ and $$$s_2$$$ are directed from $$$s_1$$$ to $$$s_2$$$. That clearly keeps the tournament not strongly connected since you can't go from $$$s_2$$$ to $$$s_1$$$. Let's start with one node in $$$s_2$$$. That means the edges incident to this node are all decided. They're all directed into it. Then, let's repeat the following: whenever we meet a flip between a node from $$$s_1$$$ and a node from $$$s_2$$$, we decide all the edges incident to the node in $$$s_1$$$, let's call it $$$u$$$. We'll choose their direction so that at the current moment, the moment of the flip, all the other nodes in $$$s_1$$$ have their edges directed into it. That effectively moves $$$u$$$ from $$$s_1$$$ to $$$s_2$$$, keeping the tournament not strongly connected. Now with the choice of base case. If you choose $$$u$$$ to be the latest node to be flipped, you'll pass subtask $$$2$$$, because the first $$$\lceil\frac{n}{2}\rceil-1$$$ flips will pass without changes, and then you can survive $$$n-2$$$ more flips. If you instead try every node to be the base case, one of them will be able to survive for $$$2n-\lfloor log_2(n) \rfloor-3$$$ flips! The proof is: you may think about our operation as follows... you start with a node, and every time a flip happens between its component and outside, its component gets extended by one node. Let's focus on the first $$$n-1$$$ flips. Let's treat the flips as undirected edges. Then, one of the components has to be a tree. Let's get the latest flip on that component. Before it, the tree was $$$2$$$ components, one of them at most half as big as the original tree. You can see by induction that this means some node's component will only get extended at most $$$\lfloor\log_2(n)\rfloor$$$ times! That obviously means you can survive $$$2n-\lfloor log_2(n) \rfloor-3$$$ flips with this node as the base case.

Open questions:

• Can you improve the analysis of the solution or find a case that pushes it to the limit I found? The smallest case I found that breaks it has $$$2n-4$$$ flips. If it helps you, you may think about it as finding a graph with the smallest number of edges such that every pair of nodes have a path with increasing weights. (UPD: solved, the solution indeed works up to $$$2n-5$$$ flips.)

• Let's look at the inverse problem: what's the shortest sequence such that no tournament can survive? The shortest I could find has length $$$2n-3$$$. It's just the sequence $$$(1,2)$$$, $$$(1,3)$$$, $$$\ldots$$$, $$$(1,n)$$$, $$$(1,2)$$$, $$$\ldots$$$, $$$(1,n-1)$$$. The proof no tournament can survive is: it's well-known every tournament has a hamiltonian path. Let's look at the sub-tournament that doesn't contain node $$$1$$$; let the hamiltonian path in it start with node $$$a$$$ and end with node $$$b$$$. It's sufficient that the edges $$$(1,a)$$$ and $$$(1,b)$$$ are directed in the way that closes a hamiltonian cycle. You can see that this sequence of flips achieves that at some moment. So now since you can always survive $$$2n-5$$$ flips but can't survive $$$2n-3$$$, what's up with $$$2n-4$$$?