Monocarp has arranged n colored marbles in a row. The color of the i-th marble is ai. Monocarp likes ordered things, so he wants to rearrange marbles in such a way that all marbles of the same color form a contiguos segment (and there is only one such segment for each color). In other words, Monocarp wants to rearrange marbles so that, for every color j, if the leftmost marble

Monocarp and Bicarp live in Berland, where every bus ticket consists of n digits (n is an even number). During the evening walk Monocarp and Bicarp found a ticket where some of the digits have been erased. The number of digits that have been erased is even. Monocarp and Bicarp have decided to play a game with this ticket. Monocarp hates happy tickets, while Bicarp collects them. A ticket is

如你所见，后缀自动机。 然而就nm看不懂，先看不懂它的图是啥，又看不懂它的边是啥，现在还是看不懂它的边是咋找出来的。可是咱不想搞不清楚它是干嘛

设$primes(x)$为x的质因数的集合。 设$g(x,p)$表示可以整除x的最大的$p^k$。 设$f(x,y)$表示将x作分解后对每个质因

给出一些点，询问对于点$(x,y)$，求其能和已知点形成多少个直角三角形。 分析 首先，对于询问的点，直接加入集合离线操作就可以。这道题就变成了

Petya recently found a game “Choose a Square”. In this game, there are nn points numbered from 11 to nn on an infinite field. The ii-th point has coordinates (xi,yi) and cost ci.

You have to choose a square such that its sides are parallel to coordinate axes, the lower left and upper right corners belong to the line y=x, and all corners have integer coordinates.

The score you get is the sum of costs of the points covered by the selected square minus the length of the side of the square. Note that the length of the side can be zero.

Petya asks you to calculate the maximum possible score in the game that can be achieved by placing exactly one square.

{% asset_img a.png %}

分析

这道题其实和多校的Snowy Smile（题文无关）挺像的。