A. LuoTianyi and the Palindrome String
Consider the substring of $$$s$$$ from the second character to the last, or $$$s_2s_3\cdots s_n$$$. If it's not palindrome, then the answer must be $$$n-1$$$. What if it's palindrome? This implies that $$$s_2=s_n$$$, $$$s_3=s_{n-1}$$$, and so on. Meanwhile, the fact that $$$s$$$ is palindrome implies $$$s_1=s_n$$$, $$$s_2=s_{n-1}$$$, etc. So we get $$$s_1=s_n=s_2=s_{n-1}=\cdots$$$ or that all characters in $$$s$$$ is the same. In this situation, every subsequence of $$$s$$$ is palindrome of course, so the answer should be $$$-1$$$.
B. LuoTianyi and the Grid
Assume that $$$n>m$$$. Greedily thinking, we want the maximum possible $$$a$$$ to appear as the maximum value of as many subtables as possible, meanwhile, we also want the minimum possible $$$a$$$ to appear as the minimum value of as many subtables as possible. This gives us two choices: making the upper-left square the minimum or the maximum. It's symmetrical so we'll only consider the minimum situation.
Now all the subtables have the same minimum value, we want to maximize the number of subtables where the maximum $$$a$$$ appears as the maximum value. Placing it at $$$(1,2)$$$ and $$$(2,1)$$$ makes the number $$$n(m-1),m(n-1)$$$ each, because $$$n>m$$$, we have $$$m(n-1)>n(m-1)$$$, so we place the largest $$$a$$$ at $$$(2,1)$$$ and the second largest at $$$(1,2)$$$, the answer for this case is $$$m(n-1)\times \max+m\times \text{second max}-mn\times\min$$$.
C. LuoTianyi and the Show
First we can notice that, if someone with a specific favourite seat(i.e. not $$$-1$$$ nor $$$-2$$$) has got his seat taken by a $$$-1$$$ guy or a $$$-2$$$ guy, it's better to let the first man go first, and the $$$-1$$$ or $$$-2$$$ one go after him.
Now, we know it's better to make those with a favourite seat go in first. After they have seated, now we consider filling the space between them with $$$-1$$$ and $$$-2$$$. It's easy to notice that we can find two non-overlapping prefix and suffix, and fill the blank seats in the prefix with $$$-1$$$, and the blanks in the suffix with $$$-2$$$. We now only need to find the answer greedily for each division point between the prefix and the suffix.
The time complexity is $$$O(n)$$$.
D. LuoTianyi and the Floating Islands
Call a node special if there is a person in it.
When $$$k$$$ is odd, we find that there is only one node satisfying the conditions.
$$$\bf{Proof}.$$$ Assume distinct node $$$x$$$ and node $$$y$$$ are good nodes. Let $$$x$$$ be the root of the tree. Define $$$s_i$$$ as the number of special nodes in subtree $$$i$$$. Think about the process we move from $$$x$$$ to $$$y$$$. If we try to move the chosen node from its father to $$$i$$$, the variation of cost is $$$k-2s_i$$$. When move from $$$x$$$ to its son $$$i$$$ which $$$s_i$$$ is maximal, $$$k-2s_i\geq 0$$$ is held (Otherwise, $$$x$$$ isn't a good node). And we can get $$$k-2s_i>0$$$ further because $$$k$$$ is odd and $$$2s_i$$$ is even. Since $$$\min_{1\leq j\leq n}{k-2s_j}=k-2s_i$$$, we find $$$k-2s_j>0$$$ for all $$$j$$$. So $$$y$$$ can't be good node.
Then think about the situation that $$$k$$$ is even. Choose a node as root arbitrarily. With the same method, we find that good nodes satisfy $$$2s_i=k$$$. It's also sufficient. Define $$$p_i$$$ as the possibility that $$$s_i=\frac{k}{2}$$$, then the answer is $$$1+\sum_{i=1}^{n}p_i$$$.
Define $$$S_i$$$ as the size of subtree $$$i$$$. When $$$s_i=\frac{k}{2}$$$, there are $$$\frac{k}{2}$$$ special nodes in subtree $$$i$$$ and $$$\frac{k}{2}$$$ in the other part. The number of ways to place special nodes is $$$\binom{n}{k}$$$, and $$$\binom{S_i}{\frac{k}{2}}\binom{n-S_i}{\frac{k}{2}}$$$ of them satisfying the condition. So $$$p_i=\dfrac{\binom{S_i}{\frac{k}{2}}\binom{n-S_i}{\frac{k}{2}}}{\binom{n}{k}}$$$.
So we can solve the problem in $$$O(n)$$$.
E. LuoTianyi and XOR-Tree
Hint: Consider a brute force dynamic programming solution and try to optimize it.
Denote the minimum number of operations needed to make every path from a leaf inside the subtree of $$$u$$$ to the root have the xor value of $$$w$$$ as $$$f_{u,w}$$$. Observe that for every $$$u$$$, there are only $$$2$$$ possible different values for $$$f_{u,w}$$$. This is because if $$$f_{u,w_1}-f_{u,w_2}>1$$$, we can use an operation of xor-ing $$$a_u$$$ with $$$w_1 \ \text{xor} \ w_2$$$ to make all the xor values from $$$w_2$$$ to $$$w_1$$$, which takes $$$f_{u,w_2}+1$$$ steps instead of $$$f_{u,w_1}$$$.
Now we only need to calculate $$$\text{minn}_u=\min f_{u,w}$$$, and the set $$$S_u$$$ of $$$w$$$ that makes $$$f_{u,w}$$$ minimum. We have $$$\text{minn}_v=0$$$ and $$$S_v={\text{the xor value from root to v}}$$$ for leaf $$$v$$$. It's trivial to calculate $$$\text{minn}_u$$$.
Note that $$$S_u$$$ contains of the numbers appearing the most times in the sets of $$$u$$$'s son. We can maintain $$$S_u$$$ using a map and merging it heuristically. Consider when merging sets into a new set $$$S'$$$. If every element of $$$S'$$$ appears only once in the original sets, then we keep $$$S'$$$ as the result, otherwise, brute force the whole set $$$S'$$$ and find the elements appearing the most times. For the second situation, every element's count of appearance is at least halved(those appearing once have $$$0$$$ and others have $$$1$$$ afterwards), so the number of brute force checking operations is $$$O(n\log n)$$$.
The final time complexity is $$$O(n\log^2 n)$$$.
F. LuoTianyi and the Function
Consider an alternative method of calculating $$$g$$$. Notice that $$$g(i,j)$$$ is the minimum of the last appearing position of all colors(let's call different values of $$$a_x$$$ colors for short) in the interval $$$[i,j]$$$.
Consider the sequence from $$$a_n$$$ to $$$a_1$$$. Adding $$$a_i$$$ to the front of the sequence only affects the values $$$g(i,x)(i\leq x<\text{nxt}_i)$$$, where $$$\text{nxt}_i$$$ is the next position after $$$i$$$ having the same $$$a$$$ value as it. Or it's to say to modify $$$g$$$ values in the submatrix of $$$[(1,i),(i,\text{nxt}_i-1)]$$$ to $$$i$$$, which can be done in $$$O(n\log^2 n)$$$, but it's not fast enough.
Because the queries happen after all modifications take place, you can store the queries offline, and calculate a submatrix using $$$4$$$ queries of submatrixes having $$$(1,1)$$$ as the upper-left corner. Now we need to maintain a data structure that can: 1. set all values in an interval as a same value $$$x$$$, 2. query the history sum(sum of values on all previous editions). We can maintain the segments of adjacent positions with the same values, and turn the modification into 'range add' for a segment.
An operation makes at most $$$O(1)$$$ new segments, and now there's only $$$O(n)$$$ range add modifications and $$$O(m)$$$ range history sum queries, now the problem can be solved in $$$O(n\log n)$$$ time complexity with segment tree.
G. LuoTianyi and Cartridge
Consider finding the maximum value of $$$B+D$$$ for every $$$\min(A,C)$$$. Denote $$$\min(A,C)$$$ as $$$x$$$. We call a vertex $$$u$$$ satisfying $$$a_u\geq x$$$ or an edge satisfying $$$c_e\geq x$$$ optional. Denote as $$$V$$$ the optional vertex set and as $$$E_0$$$ the optional edge set.
Firstly, if all optional vertices are on the same side of an edge, this edge mustn't be chosen. Delete these edges from $$$E_0$$$ and we get the edge set $$$E$$$. Formally, an edge $$$e$$$ is in $$$E$$$ if and only if $$$c_e\geq x$$$ and there exists $$$u,v$$$ so that $$$e$$$ is on the path between them.
$$$\bf{Lemma.}$$$ There exists an optimal $$$T_{\text{ans}}=(V_\text{ans},E_\text{ans})$$$ that either $$$V=V_\text{ans}$$$ or $$$E=E_\text{ans}$$$.
$$$\bf{Proof.}$$$ Assume an optimal $$$T'=(V',E')$$$ with $$$V'\neq V,E'\neq E$$$. Choose an edge $$$e$$$ that is in $$$E$$$ but not in $$$E'$$$. Because $$$V'\neq V$$$, there must exist two vertices $$$u,v$$$ on different sides of edge $$$e$$$ and $$$u\in V',v\notin V'$$$. Consider adding the edge $$$e$$$ and the vertex $$$v$$$ into our chosen tree, the resulting graph is obviously a tree. Note that $$$b_v,d_e\geq 0$$$, so the resulting choice is no worse than $$$T'$$$.
When we delete the edges in $$$E$$$ from the original tree, we get some connected components. Shrink one component into a single vertex to get $$$V'$$$, and then for all edges $$$(u,v)\in E$$$, connect $$$u$$$'s and $$$v$$$'s component together in the new graph and get $$$E'$$$. Obviously, the new graph $$$T'=(V',E')$$$ is a tree.
For any leaf vertex $$$u'$$$ on the new tree $$$T'$$$, there must exist a vertex $$$u$$$ in the component $$$u'$$$ that is chosen, otherwise the edge connecting to $$$u'$$$, let's say, $$$e'$$$ is not chosen either. Adding $$$u$$$ and $$$e'$$$ into our answer tree achieves a better answer.
Assume that now we have chosen a vertex $$$u$$$ for every leaf $$$u'$$$, denote the set of chosen vertices as $$$V_x$$$. Consider an arbitary choice of vertex for components $$$V_c$$$ and edge choice $$$E_c$$$ satisfying $$$V_x\subseteq V_c\subseteq V,E_c\subseteq E,|V_c|-1=|E_c|$$$. It's easy to prove that the choice is a legal answer, given the fact that every $$$e\in E_c$$$ has at least one leaf component on each side and every leaf component contains a chosen vertex.
Reconsider the lemma, and we can get a solution for a fixed $$$x$$$:
- Find $$$V,E$$$. Calculate the components and get $$$V',E'$$$.
- Find the vertex with the maximum $$$b$$$ in every leaf-component in $$$V'$$$ and get $$$V_x$$$.
- Let $$$m$$$ be $$$\min(|V|,|E|+1)$$$, and $$$m'$$$ be $$$|V_x|$$$. Choose the vertices in $$$V\setminus V_x$$$ with the first $$$m-m'$$$ largest $$$b$$$, and the edges in $$$E$$$ with the first $$$m-1$$$ largest $$$d$$$ and get the answer.
Consider the process when $$$x$$$ gets larger, the sets $$$V,E$$$ get smaller and smaller while the components merge into each other. We use segment trees to maintain the $$$b$$$ value of the vertices and the $$$d$$$ value of the edges, when merging two components, we simply merge the two segment trees.
The final time complexity is $$$O(n\log n)$$$.
