Oh wow, what a misconfiguration! Thanks for pointing this out. I used the "Import from Polygon contest" button to set it up, and I didn't realize that it set all the time limits to 30sec. I have updated everything and am trying to rejudge everything now.

I'm sorry for the inconvenience.

L: use a segment tree with range operations add to a[i], add to b[i], and swap(a[i], b[i])

H: dp[i][j][k] = using the elements 1..i, how many permutations have j pairs and have element i at position k. This will be O(n^3) if we use prefix sums.

For L, use a segment tree where each node stores the total sum of all open boxes, and total sum of all closed boxes. (These are the a[i] and b[i] in this comment.) Then you just have to be careful in how to propagate these updates (I had 5+ wrong submissions due to this.)

L can also be solved using treaps.
Use two treaps, one for open, one for closed boxes. Flip operation is just swapping two ranges in the two treaps.

I'm glad you liked it! It's my favorite in this set too.

In a couple of days. Sorry for the delay.

The editorials are here. Apologies for the delay.

J: Assume all edges in a query have the same weight $$$w$$$. Then look at the components after doing kruskal for all edges with weight less than $$$w$$$(each component is compressed into 1 node). The answer is the amount of edges in the spanning forest formed by the query edges. You can find the components using a persistent array(or something similar) and merging small to large in DSU, without path compression.

Group the edges by their weight and sum the answers for each of those groups.

N: Consider all cigarettes by their number subtracted by one. The condition to be touched by angel $$$i$$$ then becomes $$$A \mod 2^i>=2^{i−1}$$$ which is exactly the bit count because i becomes very large. However, we only need to consider any $$$i$$$ in range $$$[1,31]$$$.

As the next step, we define a function that $$$F(N,k)$$$ which returns both the sum of the indices and the count of indices less than $$$N$$$ with $$$k$$$ bits set. The sum and number of indices between $$$[L,R]$$$ with $$$k$$$ bits is $$$F(R,k)−F(L−1,k)$$$. My function is a bit clunky and I'm sure there is a simpler way to accomplish it, so I won't explain the inner workings here unless someone asks. The important thing is that the function works in $$$O(\log{}N)$$$ regardless of $$$k$$$.

Let $$$H(z, L, R)$$$ be the sum of the $$$z$$$ holiest indices within $$$[L, R]$$$. We will find $$$H(r_b, L, R)$$$ and then subtract the $$$H(r_{a−1}, L, R)$$$. Notice also that any number with a bit count of $$$x$$$ will be "holier" than a bit count of $$$x−1$$$. This suggests, that we iterate backwards from $$$31$$$ bits and keep the sum at each step.

To find $$$H(z, L, R)$$$, iterate $$$k$$$ from $$$[31, 0]$$$. At each step, count the sum and number of indices $$$[L, R]$$$ with k bits set (use $$$F(N, k)$$$ as defined before). If the number of indices with $$$k$$$ bits set is less than or equal to $$$z$$$, decrement $$$z$$$ by the number of indices and add sum of the indices to the final value to be returned.

However, if $$$z$$$ doesn't nicely approach 0, there is a problem. To solve it requires a final insight. Consider two indices $$$i_1 \gt i_2$$$ both with $$$k$$$ bits set. By the second condition of holy comparisons, "the last that is touched is the holiest", it can be shown that $$$i_1$$$ is always holier.

After the final insight, we can binary search on the lower bound of our interval in order find sum of the final indices. (Binary search for the lower bound $$$l$$$ such that the count of indices from $$$[l, R]$$$ with $$$k$$$ bits set is equal to the remaining number of indices that we need). Then add this number to the counter, and return.

The final complexity is $$$O(T (\log{} 10^9)^2)$$$. For each query, we iterate through the 31 possible values for $$$k$$$ bits set, and at each step we take $$$O(\log{}10^9)$$$ to count both the sum and the number of indices with $$$k$$$ bits set, except for one iteration when it takes $$$O((\log{}10^9)^2)$$$ for the binary search. But since this can happen at most once, the final complexity is still $$$O((\log{} 10^9)^2)$$$ per query.

Some care needs to be taken to minimize the constant factor (I'm not sure if it's required to pass), however the main idea there. Hopefully I was of help!