Description:

There is a colony of villains with several holes aligned in a row, where each hole contains exactly one villain. Each colony arrangement can be expressed as a string of even length, where the \(i\)-th character of the string represents the type of villain in the \(i\)-th hole. Iron Man can destroy a colony only if the colony arrangement is such that all villains of a certain type either live in the first half of the colony or in the second half of the colony. His assistant Jarvis has a special power. It can swap villains of any two holes, i.e. swap any two characters in the string; he can do this operation any number of times. Now Iron Man asks Jarvis \(q\) questions. In each question, he gives Jarvis two numbers \(x\) and \(y\). Jarvis has to tell Iron Man the number of distinct colony arrangements he can create from the original one using his powers such that all villains having the same type as those originally living in \(x\)-th hole or \(y\)-th hole live in the same half and the Iron Man can destroy that colony arrangement. Two colony arrangements are considered to be different if there exists a hole such that different types of villains are present in that hole in the arrangements.

Description:

You are given an undirected weighted connected graph with \(n\) vertices and \(m\) edges without loops and multiple edges. The \(i\)-th edge is \(e_i = (u_i, v_i, w_i)\); the distance between vertices \(u_i\) and \(v_i\) along the edge \(e_i\) is \(w_i\) (\(1 \le w_i\)). The graph is connected, i. e. for any pair of vertices, there is at least one path between them consisting only of edges of the given graph. A minimum spanning tree (MST) in case of positive weights is a subset of the edges of a connected weighted undirected graph that connects all the vertices together and has minimum total cost among all such subsets (total cost is the sum of costs of chosen edges). You can modify the given graph. The only operation you can perform is the following: increase the weight of some edge by \(1\). You can increase the weight of each edge multiple (possibly, zero) times. Suppose that the initial MST cost is \(k\). Your problem is to increase weights of some edges with minimum possible number of operations in such a way that the cost of MST in the obtained graph remains \(k\), but MST is unique (it means that there is only one way to choose MST in the obtained graph). Your problem is to calculate the minimum number of operations required to do it.

Description:

The only difference between easy and hard versions is a number of elements in the array. You are given an array \(a\) consisting of \(n\) integers. The value of the \(i\)-th element of the array is \(a_i\). You are also given a set of \(m\) segments. The \(j\)-th segment is \([l_j; r_j]\), where \(1 \le l_j \le r_j \le n\). You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array \(a = [0, 0, 0, 0, 0]\) and the given segments are \([1; 3]\) and \([2; 4]\) then you can choose both of them and the array will become \(b = [-1, -2, -2, -1, 0]\). You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array \(a\) and obtain the array \(b\) then the value \(\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i\) will be maximum possible. Note that you can choose the empty set. If there are multiple answers, you can print any. If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Description:

Vasya got really tired of these credits (from problem F) and now wants to earn the money himself! He decided to make a contest to gain a profit. Vasya has \(n\) problems to choose from. They are numbered from \(1\) to \(n\). The difficulty of the \(i\)-th problem is \(d_i\). Moreover, the problems are given in the increasing order by their difficulties. The difficulties of all tasks are pairwise distinct. In order to add the \(i\)-th problem to the contest you need to pay \(c_i\) burles to its author. For each problem in the contest Vasya gets \(a\) burles. In order to create a contest he needs to choose a consecutive subsegment of tasks. So the total earnings for the contest are calculated as follows: if Vasya takes problem \(i\) to the contest, he needs to pay \(c_i\) to its author; for each problem in the contest Vasya gets \(a\) burles; let \(gap(l, r) = \max\limits_{l \le i < r} (d_{i + 1} - d_i)^2\). If Vasya takes all the tasks with indices from \(l\) to \(r\) to the contest, he also needs to pay \(gap(l, r)\). If \(l = r\) then \(gap(l, r) = 0\). Calculate the maximum profit that Vasya can earn by taking a consecutive segment of tasks.

Description:

Vasya has a string \(s\) of length \(n\) consisting only of digits 0 and 1. Also he has an array \(a\) of length \(n\). Vasya performs the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue together the remaining parts (any of them can be empty). For example, if he erases substring 111 from string 111110 he will get the string 110. Vasya gets \(a_x\) points for erasing substring of length \(x\). Vasya wants to maximize his total points, so help him with this!

A. Lunar New Year and Cross Counting

Description:

Lunar New Year is approaching, and you bought a matrix with lots of "crosses". This matrix \(M\) of size \(n \times n\) contains only 'X' and '.' (without quotes). The element in the \(i\)-th row and the \(j\)-th column \((i, j)\) is defined as \(M(i, j)\), where \(1 \leq i, j \leq n\). We define a cross appearing in the \(i\)-th row and the \(j\)-th column (\(1 < i, j < n\)) if and only if $M(i, j) = M(i - 1, j - 1) = M(i - 1, j + 1) = M(i + 1, j - 1) = M(i + 1, j + 1) = $ 'X'. The following figure illustrates a cross appearing at position \((2, 2)\) in a \(3 \times 3\) matrix. X.X.X.X.X Your task is to find out the number of crosses in the given matrix \(M\). Two crosses are different if and only if they appear in different rows or columns.

线段树优化建图，用于区间到区间建边时降低空间复杂度 建立两颗线段树，一颗in, 代表进入这个区间，一颗out,代表从这个区间出去 in树从父亲向儿子建边，代表宏观进入整个区间，不向下寻找 out树从儿子向父亲建边，代表出去 in树向out树对应点建边，代表从这个点进去可以从它出去 建真正的边时： 1: 单点向单点: out树对应点向in树对应点建边 2: 单点向区间: out树对应点向in树对应区间建边 3: 区间向单点: out树对应区间向in树对应点建边 4: 区间向区间: out树区间对新点P建边，P向in树对应点建边