Warning: my English is very bad.
In this task you need to check the existense of such pair i and j, such that i ≠ j, a[i] < a[j], b[i] > b[j]. If such i and j exist, Alex is happy.
There is very simple solution. Let's check that for all i a[i] = b[i]. If this condition is true we should print "Poor Alex". We can easy prove it. Let's sort arrays a and b like pair of numbers in increasing order. We can see that Alex is happy if we have at least one inversion in array b, i.e there is such pair i and j that b[i] > b[j] и i < j (). i.e it means that array b is not sorted and it's means that a ≠ b.
In this task you need to calculate formula that given in the statement, but it's hard to calculate it with the naive way.
But we can transform our formula to this:
This formula is right because 5 is prime number and it's coprime with 1, 2, 3, 4.
To solve this task we should be able to calculate remainder of division n by 4 and calculate formula for small n.
Asymptotics — .
There is also another solution. It uses a fast exponentiation, but not binary exponentiation. The idea of this exponentiation is the same as that of the binary exponentiation. Let we want to fast calculate x n modP. Algorithm is very simple. Let process digits of n moving from end to begin. Let Result — current result and K — x (10 i), i — number of the currently processed digit (digits are numbered from the end. Used 0-indexation). During processing of digits, we must update result: , c[i] — i-th digit of the number n (digits are numbered from the end).
Asymptotics — .
In this task we need to maximize the sum of numbers that we took. Let precalc array cnt. cnt[x] — number of integers x in array a. Now we can easily calculate the DP:
f(i) = max(f(i - 1), f(i - 2) + cnt[i]·i), 2 ≤ i ≤ n;
f(1) = cnt;
f(0) = 0;
The answer is f(n).
Asymptotics — O(n).
To solve this problem we need the prefix tree(trie), which will have all the strings from the group. Next we will calculate the two DP: win[v] — Can player win if he makes a move now (players have word equal to prefix v in the prefix tree(trie)). lose[v] — Can player lose if he makes a move now (players have word equal to prefix v in the prefix tree(trie)).
if v is leaf of trie, then win[v] = false; lose[v] = true;
Else win[v] = (win[v] or (not win[i])); lose[v] = (lose[v] or (not lose[i])), such i — children of vertex v.
Let's look at a few cases:
If win[v] = false, then second player win (first player lose all games).
If win[v] = true и lose[v] = true, then first player win (he can change the state of the game in his favor).
If win[v] = true and lose[v] = false, then if , then first player win, else second player win.
Asymptotics — .
You can see that the road system is a forest. For efficient storage component we need to use DSU. First, we need to build the initial system of roads. For each component of the initial road system, we must find the diameter of component. This can be done using a DFS or BFS. Let a — any vertex of component. Let b — furthest vertex from vertex a. Let c — furthest vertex from vertex b. Diameter equal to distance from b to c. This algorithm for finding the diameter is correct only for tree. For each component in the DSU, we know its diameter.
Now it is very easy to answer the query of the $1$st type: To know the component which contains the vertex x and output diameter of this component. Query of the $2$nd type also very easy to process: Let u — of component in which lie the vertex x, v — of component in which lie the vertex y. If u ≠ v, then we can merge components: The diameter of the new component is computed as follows:
Asymptotics — O(n·A - 1(n)), где A - 1(n) — inverse Ackermann function.
Let's change the query type 1 to two more simple requests:
Erase a number from r-th position. Insert this number after (l - 1)-th position.
Now let's keep our array as blocks. In each block will store the numbers themselves in such a manner as in the array a and will store an array cnt. cnt[x] — number of integers x in block. This requires O(n sqrtn) space.
Now we can fast process the queries of the 1 st type. We can erase number from r-th position in operations. And we can insert this number after (l - 1)-th position in operations. Also we can fast recalc cnt after transformations.
Also we can fast process the queries of the
Unable to parse markup [type=CF_TEX]O (\ sqrt n) $ numbers are in blocks, which are partly lie within the boundaries of the query.
To keep the size of the blocks close to , we need rebuild our structure after each -th query of the 1 st type. We can rebuild structure in O(n) operations.
Asymptotics — .
In this problem you should quickly be able to compute the function described in the statement.
You may notice that this task is equivalent to next task:
Go through the array a, starting from the position of y, making (x - 1) step. Step might be: step to the left or to stay in place.
Function is calculated as follows: , k i — how many times we visited the i th element of the array a.
For a fixed l is clear, it is most optimally that a minimum on the interval [l, y] has been visited by (x - (y - l)) times, and all the other numbers once.
You may notice that optimally to a[l] was a minimum.
From all this we can conclude that for a fixed l answer is — sum[y] - sum[l] + a[l]·(x - (y - l)), where sum — an array of prefix sums of array a.
Above formula can be written as follows:
sum[y] - sum[l] + a[l]·(x - (y - l)) = sum[y] - sum[l] + a[l]·(x - y + l) = sum[y] - sum[l] + a[l]·l + a[l]·(x - y) = sum[y] + (a[l]·(x - y) + a[l]·l - sum[l])
You may notice that in brackets something like the equation of the line — K·X + B. That's very similar to the equation of the line: a[l]·(x - y) + a[l]·l - sum[l], where K = a[l], X = (x - y), B = a[l]·l - sum[l].
Now we must find minimum for all l and fixed X = (x - y).
We have n lines, i. e. for every element in array a one line (K i, B i).
Answer for query equal to:
, where (K i, B i) — i-th line. K i = a[i], B i = a[i]·i - sum[i].
For fast answer calculation we must use Convex Hull Trick with segment tree. In every vertex of segment tree we keep all lines for segment of this vertex. This requires space, because each line lies in vertices. And we can answer query in operations. Because we visit vertices and each vertex need in operations. You can learn the theory about Convex Hull Trick here.