Code: 293163701

First, notice that

• a string like $$$\texttt{RDRDRD}$$$ will change the array $$$[a,a+1,\ldots,b]$$$ to $$$[a+1,\ldots,b,a]$$$. Let's call this operation shift.
• a string like $$$\texttt{RRRDDD}$$$ will change the array $$$[a,a+1,\ldots,b]$$$ to $$$[b,b-1,a,a+1,\ldots,b-2]$$$. Let's call this operation shuffle.

Now let's start sorting the array. Suppose $$$a$$$ is a permutation of $$$1 \sim n$$$. The basic idea is, in the $$$i$$$-th turn move $$$i$$$ to the end.

Let's consider the $$$i$$$-th turn, let $$$i$$$'s current position be $$$pos$$$. Now the array looks like $$$[\ldots,i,\ldots,1,2,3,\ldots,i-1]$$$.

• In most cases, you can do a shuffle for $$$a[1,pos + 2]$$$. Now we are on $$$(pos+2,pos+2)$$$ and $$$a_{pos+2} = i$$$, then do a shift for $$$a[pos+2,n]$$$ is ok. To do this, we should have $$$pos \le n - i - 1$$$ so that the shuffle won't affect the $$$1,2,\ldots,i-1$$$ part.
• Otherwise, Let's first do a shuffle for $$$a[1,pos]$$$, and shift for $$$a[pos,n]$$$. Now $$$a_n$$$ is a random number. Then shift the whole array and we have $$$a_n = i$$$. Then shuffle the whole array, now we have $$$a_1 = i$$$ and $$$a_n = i - 1$$$, do another shift for whole array is ok. For example, we want to move $$$4$$$ to the end, we do $$$[6,5,4,1,2,3] \to [4,5,1,2,3,6] \to [5,1,2,3,6,4] \to [4,6,5,1,2,3] \to [6,5,1,2,3,4]$$$.

Please note that the first case costs us $$$1$$$ operation, but the second one costs us $$$4$$$. As a result, we may need more than $$$2n+4$$$ operations to sort finish it. Now, if we use more than $$$2n+4$$$ operations, shift $$$a[1,i]$$$, shuffle $$$a[i,n]$$$ before everything begins. Try each $$$i$$$ until we use less than $$$2n+4$$$ operations, and it get $$$\color{green}{\text{Accepted}}$$$!

I believe it can be hacked, but i don't know how. Can anyone hack it :)

When you failed to submit your code at the last second of contest, you need to wait nearly an hour for the system test... It drives me crazy.

Can we be allowed to submit code during the system test? Thank you mike :)

The basic idea is, set a value $$$B$$$, if a subtree's maxinum height is smaller than $$$B$$$ then it's useless because after $$$B$$$ queries it will jump out of the subtree. If there are $$$y$$$ sons of $$$u$$$ satisfying maxinum height greater than $$$B$$$, let's ask $$$y - 1$$$ of them and if none of these queries return $$$1$$$ then we go to the remained son's subtree. We can get a chain.

Now keep asking a leaf to make the queries number up to $$$B$$$, then $$$x$$$ is on chain we get, so do a binary search. The total queries number is $$$B + \log n$$$.

I don't know how to prove $$$\sum y - 1 \le B$$$, maybe it's totally wrong. But:

• For E1, I set $$$B = 280$$$. After I get AC, I found that there are two big bugs in my code:
• I did not use a subtree's maxinum height is smaller than $$$B$$$, but use a subtree's maxinum height is smaller than $$$B + now$$$ ($$$now$$$ is the queries number i have done) to judge if a substree is useless.
• After I get the chain, I do $$$B$$$ queries on a leaf instead of making the queries number up to $$$B$$$.
• Why this can get AC?
• For E2, I set $$$B = 140$$$. I fixed bugs above and get WA on pretest 49. After contest, I use a subtree's maxinum height is smaller than $$$B - 3$$$, to judge if a substree is useless and i get AC. Why?

My E1 code: 271595615

My E2 code: 271694519

Can anyone hack then?

Let's do HLD on the tree and now this problem is on a sequence : Given an array $$$a$$$ of length $$$m$$$, answer $$$q$$$ queries, each query gives you $$$x,y$$$ and you need to print $$$\sum \limits_{i=0}^y a_i \oplus(x+i)$$$ or $$$\sum \limits_{i=0}^y a_i \oplus(x-i)$$$.

Let's calculate the answer for each bit $$$j$$$. You can easily find that $$$x,x+1,\ldots,y$$$ in $$$j$$$-th bit looks like $$$0000111100001111\ldots$$$, set a value $$$B$$$.

• For bit $$$j \le B$$$, there are at most $$$\mathcal O(2^j)$$$ distinct $$$x$$$ (as the length of a pattern is $$$2^{j+1}$$$). Calculate all distinct $$$x$$$ by brute force and the complexity is $$$\mathcal O(\sum \limits_{j=0}^B m2^j) = \mathcal O(m2^B)$$$.
• For bit $$$j > B$$$, the same pattern repeats $$$\mathcal O(\dfrac{m}{2^j})$$$ times. Pre-calculate the prefix sum of numbers of $$$0,1$$$ in $$$a_i$$$'s $$$j$$$-th bit and we can solve a query in $$$\mathcal O(\dfrac{m}{2^j})$$$. The complexity here is $$$\mathcal O(\dfrac{mq \log n}{2^j})$$$.

Let $$$2^B = \sqrt {m \log n}$$$, The overall complexity is $$$\mathcal O((n+q) \sqrt {n \log n})$$$. But you know HLD runs really fast so it can pass the tests in $$$2.5$$$ seconds :)

Can anyone hack me? My submission.

In this blog, zh0ukangyang was banned because of the policy of using a single account. Few days passed, PinkieRabbit reached legendary grandmaster by Codeforces Round 941 (Div. 1). However, he was found as a cheater in this blog. He broke the rule of codeforces contest. We could clearly know that 'The contestants are forbidden to talk about subjects, related to the problems, with anybody, including other contestants' in Mike's blog. FIVE days passed, there is nothing happened to PinkRabbit. Is it too hard for Mike to solve this problem? I don't think so. The evidence is certain. So I can say there is no justice in codeforces?