title: [POI2013] GRA-Tower Defense Game

description:
Bytie is playing the computer game Tower Defense.

His aim is to construct guard towers, so that they protect all of his domain.

There are multiple towns in Bytie's domain, some of which are linked by  bidirectional roads.

If Bytie erects a guard tower in a city, then the tower protects its city and  all the cities directly linked with it by roads.

Just as Bytie was pondering over the placement of guard towers in his domain,  his elder sister Bytea entered the room.  She glanced at the map displayed on  the screen, and after a moment exclaimed:

"Oi, what is there to think about, clearly $k$ towers suffice!".

Angered by his sister spoiling the fun, Bytie showed his sister the door,  and began wondering what to do next.

Pride will not let him construct more than $k$ towers.

He has an up his sleeve though:

he can research a technology that will allow him to construct improved guard towers.

An improved guard tower protects not only the town it was erected in and its  immediate neighbors but also the towns that are further away.

Formally, an improved guard tower built in the town $u$ protects the town $v$ if either of the following holds:

- $u=v$;

- there is a direct road from $u$ to $v$;

- or there is such a town $w$ that there are direct roads from $u$ to $w$ and from $w$ to $v$.

Of course, Bytie still strives to erect at most $k$ towers,  but he has no qualms about making these the improved guard towers.

有一个n个点m条边的图，每条边距离是1，已知用k个攻击距离为1的塔可以打到整个地图，让构造一个方案使得用小于等于k个攻击距离为2的塔打到整个地图

inputFormat:
In the first line of the standard input, there are three integers,  $n$, $m$, and $k$ ($2\le n\le 500\ 000$,  $0\le m\le 1\ 000\ 000$, $1\le k\le n$), separated by single spaces,  that specify, respectively, the number of towns and roads in Bytie's domain,  and the number $k$ given by Bytea.

The towns in Bytie's domain are numbered from 1 to $n$.

Next,$m$ lines describing the roads follow.

Each of those lines holds two integers, $a_i$ and $b_i$ ($1\le a_i,b_i\le n$,$a_i\ne b_i$), indicating that the towns no. $a_i$ and $b_i$ are directly linked by a bidirectional road. Each pair of towns is linked by at most a single road.

outputFormat:
Your program is to print two lines, describing the placement of improved  guard towers in Bytie's domain, to the standard output.

The first line is to hold an integer $r$ ($1\le r\le k$), the number of  improved guard towers that Bytie should construct.

The second line is to specify the placement of these by providing $r$ pairwise disjoint integers that are the numbers of town where the improved  guard towers are to be built.

The town numbers can be given in an arbitrary order.

If more than one solution exists, any solution can be printed.

Let us remind that any placement of no more than $k$ improved towers will do  - you need not minimize their number.

You may assume that Bytea was correct, i.e., that the whole domain of Bytie  can indeed be protected by $k$ plain (not improved) guard towers. Thus a solution always exists.


title: [POI2013] BAJ-Bytecomputer

type: P

description:
A sequence of ![](http://main.edu.pl/images/OI20/baj-en-tex.1.png) integers ![](http://main.edu.pl/images/OI20/baj-en-tex.2.png) from the set ![](http://main.edu.pl/images/OI20/baj-en-tex.3.png) is given.

The bytecomputer is a device that allows the following operation on the sequence:

incrementing ![](http://main.edu.pl/images/OI20/baj-en-tex.4.png) by ![](http://main.edu.pl/images/OI20/baj-en-tex.5.png) for any ![](http://main.edu.pl/images/OI20/baj-en-tex.6.png).

There is no limit on the range of integers the bytecomputer can store, i.e.,    each ![](http://main.edu.pl/images/OI20/baj-en-tex.7.png) can (in principle) have arbitrarily small or large value.

Program the bytecomputer so that it transforms the input sequence into a non-decreasing sequence    (i.e., such that ![](http://main.edu.pl/images/OI20/baj-en-tex.8.png)) with the minimum number of operations.

inputFormat:
The first line of the standard input holds a single integer ![](http://main.edu.pl/images/OI20/baj-en-tex.9.png) (![](http://main.edu.pl/images/OI20/baj-en-tex.10.png)),      the number of elements in the (bytecomputer's) input sequence.

The second line contains ![](http://main.edu.pl/images/OI20/baj-en-tex.11.png) integers ![](http://main.edu.pl/images/OI20/baj-en-tex.12.png) (![](http://main.edu.pl/images/OI20/baj-en-tex.13.png))      that are the successive elements of the (bytecomputer's) input sequence, separated by single spaces.

In tests worth 24% of the total points it holds that ![](http://main.edu.pl/images/OI20/baj-en-tex.14.png),      and in tests worth 48% of the total points it holds that ![](http://main.edu.pl/images/OI20/baj-en-tex.15.png).

outputFormat: The first and only line of the standard output should give one integer,      the minimum number of operations the bytecomputer has to perform to make its input sequence non-decreasing,      of the single word BRAK (Polish for none) if obtaining such a sequence is impossible.

translation:
给定一个长度为 $n$ 的只包含 $-1,0,1$ 的数列 $a$，每次操作可以使 $a_i\gets a_i+a_{i-1}$，求最少操作次数使得序列单调不降。如果不可能通过该操作使得序列单调不降，请输出 `BRAK`。

数据范围：$1\le n\le 10^6$。


title: [POI2013] LAB-Maze

description:
Note:
During the contest, you can ask for the score of three arbitrarily chosen submissions for this problem.

Byteasar read an interesting story recently.

Its protagonist was some Greek crown princewho defeated a monster with a wool yarn,or something like that.

But something else fascinated Byteasar about the story.

What he liked most was the fact that the climax took place in a maze.

From then on Byteasar is crazy about mazes.

Byteasar sketches mazes on a squared sheet of paper.

Each sketch is a polygon with sides (representing the walls of the maze)parallel to either of the sheet's edges (i.e., the axes of the Carthesiancoordinate system), and every two successive sides are perpendicular.

Byteasar observed that if the entrance is placed on one of the sides of sucha maze, then one can traverse the whole maze and return to the entrance byalways keeping the right hand to the wall as one goes.

Moreover, throughout the maze traversal we can note the turns we take.

We shall write the letter L if we turn left when we move alongone wall to another, and P if we turn right in such case.

Byteasar wonders for which words composed of the letters L and Pthere exists a maze whose traversal results in writing this very word.

用L和P描述一个边与坐标轴平行的简单多边形，其中L表示往左拐，P表示往右拐。给定L，P的描述，请输出这个多边形。

inputFormat:
The first line of the standard input gives a single ![](http://main.edu.pl/images/OI20/lab-en-tex.1.png)-letter word(![](http://main.edu.pl/images/OI20/lab-en-tex.2.png))composed of the letters L and P, describingthe sequence of successive turns made during the maze's traversal.

In tests worth 50% of the total points an additional constraint ![](http://main.edu.pl/images/OI20/lab-en-tex.3.png) holds.

outputFormat:
If no maze corresponds to the description given as input,then the word NIE (Polish for no) is to be printedon the standard output.

Otherwise, exactly ![](http://main.edu.pl/images/OI20/lab-en-tex.4.png) lines should be printed, specifying any maze(consistent with the input) as follows.

The ![](http://main.edu.pl/images/OI20/lab-en-tex.5.png)-th of these lines is to hold two integers, ![](http://main.edu.pl/images/OI20/lab-en-tex.6.png) and ![](http://main.edu.pl/images/OI20/lab-en-tex.7.png)(![](http://main.edu.pl/images/OI20/lab-en-tex.8.png)), separated by a single space,that are the coordinates of the ![](http://main.edu.pl/images/OI20/lab-en-tex.9.png)-th vertex of the maze's sketch.

The vertices are to be printed in their counterclockwise order on the polygon's perimeter;an arbitrary vertex can be chosen as the first one, and the position of the entrance need not be indicated.


title: [POI2013] LAN-Colorful Chain

description:
Little Bytie loves to play with colorful chains.

He already has quite an impressive collection, and some of them he likes    more than the others.

Each chain consists of a certain number of colorful links.

Byteasar has noticed that Bytie's sense of aesthetics is very precise.

It turns out that Bytie finds a contiguous fragment of a chain nice if    it contains exactly    ![](http://main.edu.pl/images/OI20/lan-en-tex.1.png) links of color ![](http://main.edu.pl/images/OI20/lan-en-tex.2.png) links of color ![](http://main.edu.pl/images/OI20/lan-en-tex.3.png) links of color ![](http://main.edu.pl/images/OI20/lan-en-tex.4.png),    and moreover it contains no links of other colors.

A chain's appeal is its number of (contiguous) fragments that are nice.

By trial and error, Byteasar has determined the values ![](http://main.edu.pl/images/OI20/lan-en-tex.5.png) and ![](http://main.edu.pl/images/OI20/lan-en-tex.6.png).

Now he would like to buy a new chain, and therefore asks you to write a program to aid him in shopping.

给定一个长度为 $n$ 的序列 $a$ 和 $m$ 个条件（每个条件中包含键 $c_i$ 和值 $l_i$），要求找出满足下列条件的子串的数量并输出：

 + 条件中存在键 $c_i$ 的，要求子串中 $c_i$ 恰好出现 $l_i$ 次。

 + 条件中不存在键 $c_i$ 的，要求子串中不出现 $c_i$。

先输入 $n$ 和 $m$，再输入 $m$ 个条件的 $l_i$，然后输入 $m$ 个条件的 $c_i$，最后输入 $a_i$。

inputFormat:
The first line of the standard input gives two integers, ![](http://main.edu.pl/images/OI20/lan-en-tex.7.png) and ![](http://main.edu.pl/images/OI20/lan-en-tex.8.png)      (![](http://main.edu.pl/images/OI20/lan-en-tex.9.png)), separated by a single space.

These are the length of the chain and the length of a nice fragment's description.

The second line gives ![](http://main.edu.pl/images/OI20/lan-en-tex.10.png) integers, ![](http://main.edu.pl/images/OI20/lan-en-tex.11.png) (![](http://main.edu.pl/images/OI20/lan-en-tex.12.png)),      separated by single spaces.

The third line gives ![](http://main.edu.pl/images/OI20/lan-en-tex.13.png) integers, ![](http://main.edu.pl/images/OI20/lan-en-tex.14.png)      (![](http://main.edu.pl/images/OI20/lan-en-tex.15.png), ![](http://main.edu.pl/images/OI20/lan-en-tex.16.png) for ![](http://main.edu.pl/images/OI20/lan-en-tex.17.png)), also separated by single spaces.

The sequences ![](http://main.edu.pl/images/OI20/lan-en-tex.18.png) and ![](http://main.edu.pl/images/OI20/lan-en-tex.19.png) define a nice fragment of a chain - it has to contain exactly ![](http://main.edu.pl/images/OI20/lan-en-tex.20.png) links of color ![](http://main.edu.pl/images/OI20/lan-en-tex.21.png).

The fourth line gives ![](http://main.edu.pl/images/OI20/lan-en-tex.22.png) integers, ![](http://main.edu.pl/images/OI20/lan-en-tex.23.png) (![](http://main.edu.pl/images/OI20/lan-en-tex.24.png)),      separated by single spaces, that are the colors of successive links of      the chain.

In tests worth 50% of total points the constraint ![](http://main.edu.pl/images/OI20/lan-en-tex.25.png) holds in addition.

outputFormat: Your program is to print a single integer, the number of nice contiguous    fragments in the chain, to the first and only line of the standard output.

hint:
### 数据范围：

对于 $100\%$ 的数据，$1\leq m\leq n \leq 10^6$，$1\leq a_i,b_i,c_i\leq n$。


title: [POI2013] LAS-Laser

description:
平面上有些线段，你最多从原点射出 $k$ 条射线，穿过最多的线段，且使得每条线段最多被穿过 $1$ 次。

求最多能穿过多少线段。

inputFormat:
第一行两个整数 $k$，$n$，其中 $n$ 是线段数量。

之后 $n$ 行，每行四个整数 $x_1,y_1,x_2,y_2$ 表示一条线段。

outputFormat: 输出一个整数，表示最多能穿过几条线段。


title: [POI2013] POL-Polarization

description:
Everyone knew it would only be a matter of time.  So what?

  Faced for years on, a peril becomes the every-day reality.

It loses its meaning...

Today the letter of the Bitotian char Bittard to the Byteotian king Byteasar  was released to the public.

Bitotia requested annexation of the whole Byteotia on pain of using  the Bit Polarizing Magnet (BPM).

If used, the BPM would make each and every road in Byteotia unidirectional.

The enemy knows only too well that this could be a fatal blow to the  minimalist Byteotian infrastructure - there is a unique way between  each pair of towns.

  How badly can the BPM damage the Byteotian infrastructure?

Determine the minimum and the maximum number of such pairs of towns that  it will still be possible to travel from one of them to the other while  observing the new roads orientation.

inputFormat:
The first line of the standard input gives a single integer ![](http://main.edu.pl/images/OI20/pol-en-tex.1.png) (![](http://main.edu.pl/images/OI20/pol-en-tex.2.png)), the number of towns in Byteotia.

The ![](http://main.edu.pl/images/OI20/pol-en-tex.3.png) lines that follow describe these roads.

Each such line holds two integers, ![](http://main.edu.pl/images/OI20/pol-en-tex.4.png) and ![](http://main.edu.pl/images/OI20/pol-en-tex.5.png) (![](http://main.edu.pl/images/OI20/pol-en-tex.6.png)),  which indicate that there is a direct road (still bidirectional at the  moment) linking the towns no. ![](http://main.edu.pl/images/OI20/pol-en-tex.7.png) and ![](http://main.edu.pl/images/OI20/pol-en-tex.8.png).

In tests worth 60% of the total points, the additional constraint ![](http://main.edu.pl/images/OI20/pol-en-tex.9.png) holds;moreover, in some of those, worth 30% of the total points, it even holds that ![](http://main.edu.pl/images/OI20/pol-en-tex.10.png).

outputFormat:
Two integers should be printed to the first and only line of the standard output.

The first number should be the minimum and the second - the maximum number  of pairs of towns which could remain connected (though in one direction  only) after the roads are polarized.

translation: 给定一颗树，请给树边改成有向边，求连通的点对个数的最大最小值。点对连通，要么 $a$ 能到达 $b$，要么 $b$ 能到达 $a$。$(1\le n\le 250000)$。


title: [POI2014] BAR-Salad Bar

description:
Bytea went to a salad bar.

There are $n$ fruits one next to another on the bar counter.

Specifically, these are apples and oranges.

Bytea can pick any contiguous part of the line of fruits for her salad.

The fruits she chooses will be added to the salad either from left to right or from right to left.

As Bytea loves oranges, she requires that throughout the salad making process, the number of oranges    in it should always be no smaller than the number of apples, regardless of whether these are added %    from left to right or from right to left.

Help Bytea out by writing a program that will find the longest contiguous part of the line of fruits    that satisfies her requirements.

有一个长度为n的字符串，每一位只会是p或j。求一个最长子串，使得不管是从左往右还是从右往左取，都保证每时每刻已取出的p的个数不小于j的个数。

inputFormat:
The first line of the standard input contains a single integer $n$ ($1\le n\le 1\ 000\ 000$), denoting the number of fruits.

The next line contains a string of $n$ characters $a_1,a_2,\cdots,a_n$ ($a_i\in \{j,p\}$).

These stand for Polish names of apples and oranges: jab\l{ka} and pomara\'ncze).

Consequently, if $a_i=j$, then the $i$-th fruit in a line is an apple,      and otherwise it is an orange.

outputFormat:
The first and only line of the standard output should contain a single integer equal to the number of fruits in the longest contiguous part of the line that satisfies Bytea's requirements.

Note that it could be the case that $0$ is the correct result.


title: [POI2014] HOT-Hotels

description:
There are $n$ towns in Byteotia, connected with only $n-1$ roads.

Each road directly links two towns.

All the roads have the same length and are two way.

It is known that every town can be reached from every other town    via a route consisting of one or more (direct-link) roads.

In other words, the road network forms a tree.

Byteasar, the king of Byteotia, wants three luxury hotels    erected to attract tourists from all over the world.

The king desires that the hotels be in different towns    and at the same distance one from each other.

Help the king out by writing a program that determines the number    of possible locations of the hotel triplet in Byteotia.

inputFormat:
The first line of the standard input contains a single integer $n$ ($1\le n\le 5\ 000$),   the number of towns in Byteotia.

The towns are numbered from $1$ to $n$.

The Byteotian road network is then described in $n-1$ lines.

Each line contains two integers $a$ and $b$ ($1\le a\le b\le n$) ,   separated by a single space, that indicate there is   a direct road between the towns $a$ and $b$.

outputFormat: The first and only line of the standard output should contain a single integer    equal to the number of possible placements of the hotels.

translation: 给定一棵树，在树上选 $3$ 个点，要求两两距离相等，求方案数。


title: [POI2014] KLO-Bricks

description:
Little Bitie and his friends spent the whole yesterday playing    with colorful bricks in the kindergarten.

Initially they made building models but they quickly got bored with that.

Then they decided to place the bricks in a line, one after another.

To avoid a dull look, they tried to avoid putting two bricks of the same    color next to each other.

After a long while they succeeded in placing all the bricks while observing    this rule.

Then the day care was over, and the children went home with their parents.

Today Bitie came to the kindergarten early.

He was satisfied to see that their yesterday's creation was still standing.

But then he tripped over in a most unfortunate way,    falling right on the line of bricks, which all mixed in a pile.

The boy quickly sorted them by color and wondered how best to quickly    reassemble the perfect line.

He managed to recall what were the colors of the two bricks on both end of the line.

Help little Bitie out and tell him how to order the bricks in a line so that    no two bricks of the same color are next to each other and the bricks at the ends    of the line have the colors that he recalled.

Note that Bitie could have made a mistake in recalling the two colors    or perhaps he did not find some of the blocks after falling into them,    so the reconstruction might not be possible.

给你每种颜色的砖块数量，相同颜色的砖块不能放在一起，两头颜色已经确定，构造一种方案

inputFormat:
There are three integers in the first line of the standard input,    $k$,$p$, and $q$ ($1\le k\le 1 000 000$,$1\le p,q\le k$), separated by single spaces,    denoting the number of brick colors, and the colors of    the first and the last brick in the desired arrangement, respectively.

In the second line, there are $k$ integers,$i_{1},i_{2},...,i{k}$ ($1\le i_{j}\le 1 000 000$),    separated by single spaces.

The number $i_{j}$ signifies that Bitie has exactly $i_{j}$ bricks    of color $j$.

You may assume that the total number of bricks does not exceed one million, i.e., that $n=i_1+i_2+\cdots+i_k\le 1\ 000\ 000$.

outputFormat:
Your program should print $n$ integers to the standard output,    separated by single spaces.

The numbers should represent the colors of successive bricks in    an arrangement that satisfies aforementioned constraints.

If no such arrangement exists, your program should print only    a single integer: $0$.

If there are several correct answers, your program can pick one    arbitrarily.

**在最后一个数字后请不要输出空格**

hint:
给你每种颜色的砖块数量，相同颜色的砖块不能放在一起，两头颜色已经确定，构造一种方案

由zhouyonglong提供SPJ


title: [POI2014] KUR-Couriers

description:
Byteasar works for the BAJ company, which sells computer games.

The BAJ company cooperates with many courier companies    that deliver the games sold by the BAJ company to its customers.

Byteasar is inspecting the cooperation of the BAJ company with the couriers.

He has a log of successive packages with the courier company that made the delivery    specified for each package.

He wants to make sure that no courier company had an unfair advantage over the others.

If a given courier company delivered more than half of all packages sent in some period of time,    we say that it dominated in that period.

Byteasar wants to find out which courier companies dominated in certain periods of time, if any.

Help Byteasar out!

Write a program that determines a dominating courier company or that there was none.

给一个数列，每次询问一个区间内有没有一个数出现次数超过一半

inputFormat:
The first line of the standard input contains two integers, ![](http://main.edu.pl/images/OI21/kur-en-tex.1.png) and ![](http://main.edu.pl/images/OI21/kur-en-tex.2.png) (![](http://main.edu.pl/images/OI21/kur-en-tex.3.png)),    separated by a single space, that are the number of packages shipped by the BAJ company    and the number of time periods for which the dominating courier is to be determined, respectively.

The courier companies are numbered from ![](http://main.edu.pl/images/OI21/kur-en-tex.4.png) to (at most) ![](http://main.edu.pl/images/OI21/kur-en-tex.5.png).

The second line of input contains ![](http://main.edu.pl/images/OI21/kur-en-tex.6.png) integers, ![](http://main.edu.pl/images/OI21/kur-en-tex.7.png) (![](http://main.edu.pl/images/OI21/kur-en-tex.8.png)),    separated by single spaces;    ![](http://main.edu.pl/images/OI21/kur-en-tex.9.png) is the number of the courier company that delivered the ![](http://main.edu.pl/images/OI21/kur-en-tex.10.png)-th package (in shipment chronology).

The ![](http://main.edu.pl/images/OI21/kur-en-tex.11.png) lines that follow specify the time period queries, one per line.

Each query is specified by two integers, ![](http://main.edu.pl/images/OI21/kur-en-tex.12.png) and ![](http://main.edu.pl/images/OI21/kur-en-tex.13.png) (![](http://main.edu.pl/images/OI21/kur-en-tex.14.png)),    separated by a single space.

These mean that the courier company dominating in the period between the shipments of the    ![](http://main.edu.pl/images/OI21/kur-en-tex.15.png)-th and the ![](http://main.edu.pl/images/OI21/kur-en-tex.16.png)-th package, including those, is to be determined.

In tests worth ![](http://main.edu.pl/images/OI21/kur-en-tex.17.png) of total score, the condition ![](http://main.edu.pl/images/OI21/kur-en-tex.18.png) holds,    and in tests worth ![](http://main.edu.pl/images/OI21/kur-en-tex.19.png) of total score ![](http://main.edu.pl/images/OI21/kur-en-tex.20.png).

outputFormat:
The answers to successive queries should be printed to the standard output, one per line.

(Thus a total of ![](http://main.edu.pl/images/OI21/kur-en-tex.21.png) lines should be printed.)    Each line should hold a single integer: the number of the courier company that dominated    in the corresponding time period, or ![](http://main.edu.pl/images/OI21/kur-en-tex.22.png) if there was no such company.

translation:
给一个长度为 $n$ 的正整数序列 $a$。共有 $m$ 组询问，每次询问一个区间 $[l,r]$ ，是否存在一个数在 $[l,r]$ 中出现的次数严格大于一半。如果存在，输出这个数，否则输出 $0$。

$1 \leq n,m \leq 5 \times 10^5$，$1 \leq a_i \leq n$。


title: [POI2014] WAZ-Snake

description:
A snake fills a ![](http://main.edu.pl/images/OI21/waz-en-tex.1.png) board completely.

Successive segments of the snake are numbered from ![](http://main.edu.pl/images/OI21/waz-en-tex.2.png) to ![](http://main.edu.pl/images/OI21/waz-en-tex.3.png).

The segments with successive numbers (i.e., 1 and 2, 2 and 3, 3 and 4...) occupy squares  that share an edge.

For example, a snake can fill a ![](http://main.edu.pl/images/OI21/waz-en-tex.4.png) board as follows:

The snake's segment numbers in some of the squares have been erased.

  Can you reconstruct the snake?

一只蛇被放在了一块3\*n的木板上（填充满了），蛇被分为多个小段，小段的编号是1到3n。比如说蛇可以填写一个3\*9的木板，如下所示：

部分木板上的蛇段已删遮挡。

你能重建蛇吗？

inputFormat:
In the first line of the standard input, there is a single integer ![](http://main.edu.pl/images/OI21/waz-en-tex.5.png)  (![](http://main.edu.pl/images/OI21/waz-en-tex.6.png)), the length of the board.

The three lines that follow describe the board;  the ![](http://main.edu.pl/images/OI21/waz-en-tex.7.png)-th of them contains ![](http://main.edu.pl/images/OI21/waz-en-tex.8.png) integers ![](http://main.edu.pl/images/OI21/waz-en-tex.9.png)  (![](http://main.edu.pl/images/OI21/waz-en-tex.10.png) for ![](http://main.edu.pl/images/OI21/waz-en-tex.11.png)).

If ![](http://main.edu.pl/images/OI21/waz-en-tex.12.png), then ![](http://main.edu.pl/images/OI21/waz-en-tex.13.png) is the number of the snake's segment  occupying the ![](http://main.edu.pl/images/OI21/waz-en-tex.14.png)-th square of the ![](http://main.edu.pl/images/OI21/waz-en-tex.15.png)-th row of the board.

If on the other hand ![](http://main.edu.pl/images/OI21/waz-en-tex.16.png), then the number of the snake's segment  on this square is unknown.

In tests worth 15% of the total score ![](http://main.edu.pl/images/OI21/waz-en-tex.17.png) holds,  in those worth 40% of the total score ![](http://main.edu.pl/images/OI21/waz-en-tex.18.png) holds,  and finally, in those worth 70% of the total score ![](http://main.edu.pl/images/OI21/waz-en-tex.19.png) holds.

在标准输入的第一行中，有一个整数n（1<=n<=1000），即板的长度。

下面三行描述木板的情况，第i行是n个整数aij（0<=aij<=3n）(1<=j<=n)。

如果aij大于0，那么aij就是蛇段的第aij部分

如果aij=0，那么这个蛇段就是我们不知道的

outputFormat:
Your program is to print three lines to the standard output.

The ![](http://main.edu.pl/images/OI21/waz-en-tex.20.png)-th lines should hold ![](http://main.edu.pl/images/OI21/waz-en-tex.21.png) positive integers ![](http://main.edu.pl/images/OI21/waz-en-tex.22.png) (for ![](http://main.edu.pl/images/OI21/waz-en-tex.23.png)).

All the numbers ![](http://main.edu.pl/images/OI21/waz-en-tex.24.png) together should be a permutation of the numbers from ![](http://main.edu.pl/images/OI21/waz-en-tex.25.png) to ![](http://main.edu.pl/images/OI21/waz-en-tex.26.png).

The output numbers should be a valid reconstruction of the snake, i.e., they should  be consistent with the (positive) input numbers and satisfy aforementioned constraints.

You may assume that there is at least one valid reconstruction of the snake.

If there is more than one, your program can print any valid reconstruction.

将所有aij为0的蛇段补齐


title: [POI2014] KAR-Cards

description:
There are $n$ cards arranged on a table in a certain order.

Two integers are written on each card, one per side: the obverse and the reverse.

Initially all cards lie with the averse facing up.

Byteasar, The Great Illusionist, intends to perform (multiple times!) his signature    Binary Search Card Manipulation.  However, to present it, he needs the sequence of numbers    as seen on the cards to be non-decreasing.

Thus, Byteasar may have to turn over some cards so that the numbers on their reverse sides    become visible.

Furthermore, the illusion requires a participant from the audience.

Alas, some of the volunteers are deployed by Byteasar's competitors who want him to fail.

Each such supposititious volunteer, upon entering the scene, would swap two cards on the table in a lightning move of a hand.  After each such swap, Byteasar can again turn over any cards he desires but nevertheless, he may not be able to perform his great illusion.

If that were to happen, he would be forced to turn to traditional illusions, such as pulling a rabbit out of a hat.

Write a program that determines, after each card swap, if Byteasar can perform his great illusion.

有一些卡牌，正反各有一个数，你可以任意翻转，每次操作会将两张卡牌的位置调换，你需要在每次操作后回答以现在的卡牌顺序能否通过反转形成一个单调不降的序列

inputFormat:
In the first line of the standard input, there is a single integer, $n$ ($2\le n\le 200\ 000$), the number of the cards.

The $n$ lines that follow describe the cards, one per line,in the order they are arranged on the table.

The $i$-th of these lines has two integers $x_i$ and $y_i$ ($0\le x_i,y_i\le 10^7$), separated by a single space.

These are the numbers written on the $i$-th card:

$x_i$ is the one written on the obverse and $y_i$ the one on the reverse.

The initial sequence of cards may not allow performing the great illusion.

Afterwards, there is a line with a single integer $m$ ($1\le m\le 1\ 000\ 000$), the number of card swaps.The $m$ lines that follow describe the swaps: $j$-th of these lines has two integers $a_j$ and $b_j$ ($1\le a_j,b_j\le n$), separated by a single space, indicating that the $j$-th (supposititious) volunteer will swap the $a_j$-th and the $b_j$-th cards.

outputFormat:
Your program should print $m$ lines to the standard output, each containing a single word:

TAK (Polish for yes) or NIE (Polish for no).

The $j$-th line should read TAK if Byteasar can obtain a non-decreasing sequence      of numbers by turning the cards over after the $j$-th card swap.  If he cannot,      the line should read NIE.


title: [POI2014] PRZ-Criminals

description:
Byteburg is a beautiful town by a river.

There are $n$ houses along the river, numbered downstream with successive integers from $1$ to $n$.

Byteburg used to be a nice quiet town in which everyone was happy.

Alas, this changed recently, as two dangerous criminals - Bitie and Bytie set up shop in it.

They did so many robberies already that the citizens are afraid to leave their houses.

Bitie and Bytie do no mere burglaries but rather whole raids: each time they leave their houses and walk towards each other, never turning back.

Bitie walks downstream (towards larger numbers) while Bytie walks upstream (towards smaller numbers).

Along the way, before they meet, each chooses several houses to break into and steal precious items    (and vital data).

After the robberies they meet in a house and divide their loot.

Byteburgers are sick of this already - they would all rather have their tranquility restored.

So they asked the detective Bythony for help.

The detective established that the bandits live in houses of the same color but he does not know which one.

Just a moment ago, an anonymous tip claimed that the robbers are on a raid.

Fearing for their own safety, the source did not say which houses will be broken into.

They did however specify their colors.

As it turns out, the bandits are quite superstitious - each of them will rob a house of each color at most once.

Bythony can wait no longer.

He intends to ambush the criminals at their meeting place.

Aid Bythony in his undertaking by writing a program to find all possible meeting places of the robbers.

inputFormat:
There are two integers in the first line of the standard input, $n$ and $k$ ($3\le n\le 1\ 000\ 000$, $1\le k\le 1\ 000\ 000$, $k\le n$),  separated by a single space, that specify the number of houses and the number of house colors  in Byteburg respectively.

The colors are number with successive integers from $1$ to $k$.

In the second line of input, there is a sequence of $n$ integers, $c_1,c_2,\cdots,c_n$ ($1\le c_i\le k$), separated by single spaces.

These are the colors of successive houses in Byteburg.

In the third line of input, there are two integers $m$ and $l$($1\le m,l\le n$,$m+l\le n-1$), separated by a single space, specifying the numbers of houses (to be) broken into by Bitie and Bytie respectively. In the fourth line of input, there are $m$ pairwise different integers $x_1,x_2,\cdots,x_m$($1\le x_i\le k$), separated by single spaces. These are the colors of houses robbed by Bitie in the order of being broken into (i.e., excluding Bitie's house). In the fifth, which is the last, line of input, there are $l$ pairwise different integers $y_1,y_2,\cdots,y_l$ ($1\le y_i\le k$), separated by single spaces. These are the colors of houses robbed by Bytie in the order of being broken into (again, these do not include Bytie's house). Moreover, $x_m=y_l$ is the color of the house in which the robbers will divide the plunder. (Clearly, they have to break into that one as well!)

outputFormat:
Your program it to print exactly two lines to the standard output.

The first of those should give the number of houses in which the criminals can meet  while respecting aforementioned constraints.

The second line should contain the increasing sequence of the numbers of those houses,  separated by single spaces.

If the robbers cannot meet at all, the first line should contain the number 0 while the second one should be empty.

translation:
## 题目描述

两个罪犯 Bitie 和 Bytie 抢劫 $n$ 个房子，每个房子有一个颜色，Bitie 从低编号到高编号，Bytie 从高编号到低编号，直到相遇为止。已知罪犯开始时所在房子颜色相同（但不知道是什么颜色），并且知道罪犯依次抢劫的所有房子的颜色，且每个罪犯对每种颜色的房子分别最多抢劫一次，求所有可能的相遇点。

## 输入格式

第一行两个整数 $n,k$ ，分别表示房子的个数和不同的颜色数。颜色以从 $1$ 到 $k$ 的整数标号。

接下来一行有 $n$ 个整数 $c_1,c_2,...,c_n (1 \le c_i \le k)$，表示房子的颜色。

第三行有两个整数 $m,l (1 \le m,l \le n,m+l \le n-1)$，分别表示 Bitie 和 Bytie 抢劫房子的个数。

第四行有 $m$ 个两两不同的整数 $x_1, x_2, ..., x_m (1 \le x_i \le k)$，表示 Bitie 抢劫房子的颜色（不包括 Bitie 开始时所在房子的颜色）。

第五行有 $l$ 个两两不同的整数 $y_1, y_2, ..., y_l (1 \le y_i \le k)$，表示 Bytie 抢劫房子的颜色 （不包括 Bytie 开始时所在房子的颜色）。

保证 $x_m = y_l$。

## 输出格式

输出两行，第一行一个整数，表示可能相遇的房子个数，第二行升序输出可能相遇的房子编号。


title: [POI2014] SUP-Supercomputer

description:
Byteasar has designed a supercomputer of novel architecture.

```plain
It may comprise of many (identical) processing units.
```
Each processing unit can execute a single instruction per time unit.

The programs for this computer are not sequential but rather have a tree structure.

Each instruction may have zero, one, or multiple subsequent instructions,    for which it is the parent instruction.

The instructions of the program can be executed in parallel on all available    processing units.  Moreover, they can be executed in many orders: the only    restriction is that an instruction cannot be executed unless its parent    instruction has been executed before.  For example, as many subsequent    instructions of an instruction that has been executed already can be    executed in parallel as there are processing units.

Byteasar has a certain program to run.  Since he likes utilizing his resources    optimally, he is wondering how the number of processing units would affect the running time.

He asks you to determine, for a given program and number of processing units,    the minimum execution time of the program on a supercomputer with this many processing units.

给定一棵N个节点的有根树，根节点为1。Q次询问，每次给定一个K，用最少的操作次数遍历完整棵树，输出最少操作次数。每次操作可以选择访问不超过K个未访问的点，且这些点的父亲必须在之前被访问过。

inputFormat:
In the first line of standard input, there are two integers, $n$ and $q$ ($1\le n,q\le 1\ 000\ 000$), separated by a single space, that specify the number of    instructions in Byteasar's program and the number of running time queries (for different numbers    of processing units).

In the second line of input, there is a sequence of $q$ integers, $k_1,k_2,\cdots,k_q$ ($1\le k_i\le 1\ 000\ 000$), separated by single spaces: $k_i$ is the number of processing units in    Byteasar's $i$-th query.

In the third and last input line, there is a sequence of $n-1$ integers, $a_2,a_3,\cdots,a_n$($1\le a_i<i$) separated by single spaces: $a_i$ specifies the number of the parent instruction of the instruction number $i$. The instructions are numbered with successive integers from 1 to $n$, where the instruction no. 1 is the first instruction of the program.

outputFormat:
Your program should print one line consisting of $q$ integers, separated by single spaces,    to the standard output:

the $i$-th of these numbers should specify the minimum execution time of the program on a supercomputer with $k_i$ processing units.

translation:
给定一棵 $n$ 个节点的有根树，根节点为 $1$。$q$ 次询问，每次给定一个 $k$，用最少的操作次数遍历完整棵树，输出最少操作次数。每次操作可以选择访问不超过 $k$ 个未访问的点，且这些点的父亲必须在这次操作之前被访问过。

$n, q \leq 10^6$。


title: [POI2014] PTA-Little Bird

description:
In the Byteotian Line Forest there are $n$ trees in a row.

On top of the first one, there is a little bird who would like to fly over to the top of the last tree.

Being in fact very little, the bird might lack the strength to fly there without any stop.

If the bird is sitting on top of the tree no. i, then in a single flight leg it can fly toany of the trees no. $i+1,i+2,\cdots,i+k$, and then has to rest afterward.

Moreover, flying up is far harder to flying down.  A flight leg is tiresome if it ends in a tree at leastas high as the one where is started.  Otherwise the flight leg is not tiresome.

The goal is to select the trees on which the little bird will land so that the overall flight is leasttiresome, i.e., it has the minimum number of tiresome legs.

We note that birds are social creatures, and our bird has a few bird-friends who would also like to getfrom the first tree to the last one.  The stamina of all the birds varies,so the bird's friends may have different values of the parameter $k$.

Help all the birds, little and big!

inputFormat:
There is a single integer $n$ ($2\le n\le 1\ 000\ 000$) in the first line of the standard input:

the number of trees in the Byteotian Line Forest.

The second line of input holds $n$ integers $d_1,d_2,\cdots,d_n$ ($1\le d_i\le 10^9$)separated by single spaces: $d_i$ is the height of the i-th tree.

The third line of the input holds a single integer $q$ ($1\le q\le 25$): the number of birds whoseflights need to be planned.

The following $q$ lines describe these birds: in the $i$-th of these lines, there is an integer $k_i$ ($1\le k_i\le n-1$) specifying the $i$-th bird's stamina. In other words, the maximum number of trees that the $i$-th bird can pass before it has to rest is $k_i-1$.

outputFormat:
Your program should print exactly $q$ lines to the standard output.

In the $i$-th line, it should specify the minimum number of tiresome flight legs of the $i$-th bird.

translation:
有 $n$ 棵树排成一排，第 $i$ 棵树的高度是 $d_i$。

有 $q$ 只鸟要从第 $1$ 棵树到第 $n$ 棵树。

当第 $i$ 只鸟在第 $j$ 棵树时，它可以飞到第 $j+1, j+2, \cdots, j+k_i$ 棵树。

如果一只鸟飞到一颗高度大于等于当前树的树，那么它的劳累值会增加 $1$，否则不会。

由于这些鸟已经体力不支，所以它们想要最小化劳累值。

### 输入格式

第一行输入 $n$。

第二行 $n$ 个数，第 $i$ 个数表示 $d_i$。

第三行输入 $q$。

接下来 $q$ 行，每一行一个整数，第 $i$ 行的整数为 $k_i$。

### 输出格式

共 $q$ 行，每一行输出第 $i$ 只鸟的最小劳累值。

### 数据范围

$1 \le n \le 10^6$，$1 \le d_i \le 10^9$，$1 \le q \le 25$，$1 \le k_i \le n - 1$。


title: [POI2014] RAJ-Rally

description:
  An annual bicycle rally will soon begin in Byteburg.

The bikers of Byteburg are natural long distance cyclists.

Local representatives of motorcyclists, long feuding the cyclists,  have decided to sabotage the event.

There are ![](http://main.edu.pl/images/OI21/raj-en-tex.1.png) intersections in Byteburg, connected with one way streets.

Strangely enough, there are no cycles in the street network - if one can ride from  intersection ![](http://main.edu.pl/images/OI21/raj-en-tex.2.png) to intersection ![](http://main.edu.pl/images/OI21/raj-en-tex.3.png), then it is definitely impossible to get from ![](http://main.edu.pl/images/OI21/raj-en-tex.4.png) to ![](http://main.edu.pl/images/OI21/raj-en-tex.5.png).

The rally's route will lead through Byteburg's streets.

The motorcyclists plan to ride their blazing machines in the early morning of the rally day  to one intersection and completely block it.

The cyclists' association will then of course determine an alternative route  but it could happen that this new route will be relatively short,  and the cyclists will thus be unable to exhibit their remarkable endurance.

Clearly, this is the motorcyclists' plan - they intend to block such an intersection  that the longest route that does not pass through it is as short as

inputFormat: In the first line of the standard input, there are two integers, N and M(2<=N<=500 000,1<=M<=1 000 000), separated by a single space, that specify the number of intersections and streets in Byteburg. The intersections are numbered from   to  . The   lines that follow describe the street network: in the  -th of these lines, there are two integers, Ai, Bi(1<=Ai,Bi<=N,Ai<>Bi), separated by a single space, that signify that there is a one way street from the intersection no. Ai to the one no. Bi

outputFormat:
The first and only line of the standard output should contain two integers separated by a single space.

The first of these should be the number of the intersection that the motorcyclists should block,  and the second - the maximum number of streets that the cyclists can then ride along in their rally.

If there are many solutions, your program can choose one of them arbitrarily.

translation:
### 题目描述

给定一个 $n$ 个点 $m$ 条边的有向无环图，每条边长度都是 $1$。

请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。

### 输入格式

第一行包含两个正整数 $n$，$m$（$2\le n\le5\times10^5$，$1\le m\le10^6$），表示点数、边数。

接下来 $m$ 行每行包含两个正整数 $a_i,b_i$（$1\le a_i,b_i\le n,a_i\ne b_i$），表示 $a_i$ 到 $b_i$ 有一条边。

### 输出格式

包含一行两个整数 $x$，$y$，用一个空格隔开，$x$ 为要删去的点，$y$ 为删除 $x$ 后图中的最长路径的长度，如果有多组解请输出任意一组。

hint: 感谢@zyh2015 提供spj


title: [POI2014] FAR-FarmCraft

description:
In a village called Byteville, there are $n$ houses connected with $n-1$ roads.

For each pair of houses, there is a unique way to get from one to another.

The houses are numbered from 1 to $n$.

The house no. 1 belongs to the village administrator Byteasar.

As part of enabling modern technologies for rural areas framework, $n$ computers have been delivered    to Byteasar's house.

Every house is to be supplied with a computer, and it is Byteasar's task to distribute them.

The citizens of Byteville have already agreed to play the most recent version of FarmCraft (the game) as soon as they have their computers.

Byteasar has loaded all the computers on his pickup truck and is about to set out to deliver the goods.

He has just the right amount of gasoline to drive each road twice.

In each house, Byteasar leaves one computer, and immediately continues on his route.

In each house, as soon as house dwellers get their computer, they turn it on and install FarmCraft.

The time it takes to install and set up the game very much depends on one's tech savviness, which is fortunately known for each household.

After he delivers all the computers, Byteasar will come back to his house and install the game on his computer.

The travel time along each road linking two houses is exactly 1 minute, and (due to citizens' eagerness to play) the time to unload a computer is negligible.

Help Byteasar in determining a delivery order that allows all Byteville's citizens    (including Byteasar) to start playing together as soon as possible.

In other words, find an order that minimizes the time when everyone has FarmCraft installed.

inputFormat:
The first line of the standard input contains a single integer $n$($2\le n\le 500\ 000$) that gives the number of houses in Byteville.

The second line contains $n$ integers $c_1,c_2,\cdots,c_n$ ($1\le c_i\le 10^9$),separated by single spaces; $c_i$ is the installation time (in minutes) for the dwellers of house no. i.

The next $n-1$ lines specify the roads linking the houses.

Each such line contains two positive integers $a$ and $b$ ($1\le a<b\le n$), separated by a single space.These indicate that there is a direct road between the houses no. $a$ and $b$.

outputFormat:
The first and only line of the standard output should contain a single integer:

the (minimum) number of minutes after which all citizens will be able to play FarmCraft together.

translation:
### 题目描述

在一个叫做比特村的小村庄中，有 $n-1$ 条路连接着这个村庄中的全部 $n$ 个房子。

每两个房子之间都有一条唯一的通路。这些房子的编号为 $1$ 至 $n$。

$1$ 号房子属于村庄的管理员比特安萨尔。

为了提升村庄的科技使用水平，$n$ 台电脑被快递到了比特安萨尔的房子。每个房子都应该有一台电脑，且分发电脑的任务就落在了比特安萨尔的肩上。

比特村的居民一致同意去玩农场物语这个游戏的最新快照版，而且好消息是他们很快就要得到他们最新的高配置电脑了。

比特安萨尔将所有电脑都装在了他的卡车上，而且他准备好完成这个艰巨的任务了。

**他的汽油恰好够走每条路两遍。**

在每个房子边，比特安萨尔把电脑贴心的配送给居民，且立即前往下一个房子。（配送过程不花费任何时间）

只要每间房子的居民拿到了他们的新电脑，它们就会立即开始安装农场物语。安装农场物语所用的时间根据居民的科技素养而定。幸运的是，每间房子中居民的科技素养都是已知的。

在比特安萨尔配送完所有电脑后，他会回到他自己的 $1$ 号房子去安装他自己的农场物语。

用卡车开过每条路的时间恰好是 $1$ 分钟，而居民开电脑箱的时间可以忽略不计。（因为他们太想玩农场物语了）

请你帮助比特安萨尔算出从开始配送到所有居民都玩上了农场物语的最少时间。

### 输入格式

第一行包含一个整数 $n(2 \leq n \leq 5\times 10^5)$，代表比特村中有多少房子。

第二行包含 $n$ 个整数 $c_1, c_2, ⋯, c_n(1 \leq c_i \leq 10^9)$，每个数都被单个空格隔开。$c_i$ 是第 $i$ 号房间中居民安装农场物语所用的时间。

接下来的 $n-1$ 行代表了每一条路的两个顶点。两个顶点 $a$ 和 $b$ 满足 $1 \leq a < b \leq n$，两个数之间有一个空格。

### 输出格式

一行，包含一个整数，代表题目中所说的最小时间。

感谢@deadpool123 提供的翻译

hint:
 ![](https://cdn.luogu.com.cn/upload/pic/6971.png)

给一棵树，走过每条边需要花费一个时间，安装软件又需要花费一个时间，需要遍历整棵树并回到起点，想让所有点中到达时间+安装时间的最大值最小，问这个值是多少


title: [POI2014] DOO-Around the world

description:
After trying hard for many years, Byteasar has finally received a pilot license.

To celebrate the fact, he intends to buy himself an airplane and fly around the planet  3-SATurn (as you may have guessed, this is the planet on which Byteotia is located).

Specifically, Byteasar plans to fly along the equator.

Unfortunately, the equator is rather long, necessitating refuels.

  The flight range (on full tank) of each aircraft is known.

There is a number of airports along the equator, and a plane can be refueled when it lands on one.

Since buying an airplane is a big decision, Byteasar asks your help.

He is about to present you with a list of different plane models he is considering.

Naturally, these differ in their flight range.

For each plane model, he would like to know the minimum number of landings  (including the final one) he would have to make in order to complete the journey.

Note that for each airplane model, the journey may start at a different airport.

通过几年的努力，Byteasar最终拿到了飞行员驾驶证。为了庆祝这一事实，他打算买一架飞机并且绕Byteotia星球赤道飞行一圈。但不幸的是赤道非常长所以需要中途加几次油。现在已知赤道上面所有飞机场，所有飞机从飞机场起飞降落也可以加油。因为买飞机是个十分重大的决定，Byteasar决定寻求你的帮助。他将会让你模拟不同的飞行路线。自然这些飞机一次能走的航程是不同的。对于每次模拟，他想要知道最少需要降落多少次（包括最后一次）。需要注意的是起点可以任意选取。

inputFormat:
The first line of the standard input contains two integers $n$ and $s$ ($2\le n\le 1\ 000\ 000$, $1\le s\le 100$),separated by a single space,  denoting the number of airports along the equator and the number of airplane models Byteasar is considering.

The second line contains $n$ positive integers $l_1,l_2,\cdots,l_n$ ($l_1+l_2+\cdots+l_n\le 10^9$), separated by single spaces, specifying the distances between successive airports along the equator.

The number $l_i$ is the distance between the $i$-th and $(i+1)$-st (or $n$-th and first if $i=n$) in kilometers.

The third line contains $s$ integers $d_1,d_2,\cdots,d_s$ ($1\le d_i\le l_1+l_2+\cdots+l_n$), separated by single spaces. The number $d_i$ is the $i$-th airplane model's flight range in kilometers, i.e., the maximum distance it can fly before landing and refueling.

outputFormat: Your program should print $s$ lines to the standard output: the $i$-th of these should contain a single integer, namely, the minimum lumber of flight segments (and thus also landings) necessary to fly the $i$-th airplane around the planet 3-SATurn along the equator, starting at an airport of choice, or the word NIE (Polish for no) if it is impossible to complete the journey with this airplane.


title: [POI2014] MRO-Ant colony

background: [English Edition](/paste/44plylwf)

description:
正在寻找食物的蚂蚁们来到了一座山。

这座山有 $n$ 个洞穴，并有 $n-1$ 条道路连接这些洞穴。也就是说，所有的洞穴和道路组成了一个树形结构。

对于每个只有一条道路连接的洞穴，都有一个出入口使得该洞穴与外界相连。

在**每个出入口**处，都有 $g$ 群蚂蚁，第 $i$ 群蚂蚁的大小为 $m_i$。

蚂蚁群会一个接一个地进入山中，当且仅当山中没有蚂蚁，下一群蚂蚁才会进入。

进入山后，蚂蚁们会按如下方式行动：

- 如果蚂蚁们进入了一个洞穴，该洞穴有 $d$ 条道路与之相连（不包括它们进入该洞穴经过的道路），则蚂蚁们会分为大小相等的 $d$ 个蚁群，每个蚁群各选择一条道路，使得一个道路恰好有一条蚁群经过，特别地，如果 $d=0$（即蚁群到达了出口），蚂蚁们会从该出口离开山。
- 根据上文，假如这个蚁群有 $x$ 只蚂蚁，则每个蚁群会有 $\left \lfloor \dfrac{x}{d} \right \rfloor$ 只蚂蚁，多余的蚂蚁将会消失（至于怎么消失，这并不重要 :)）。

下面这张图就是一个例子：大小为 $m$ 的蚁群到达了一个洞穴，该洞穴有 $3$ 条道路（除了它们进入该洞穴时经过的道路），则该蚁群分割成了三个大小为 $\left \lfloor \dfrac{m}{3} \right \rfloor$ 的蚁群。

![](https://cdn.luogu.com.cn/upload/pic/6972.png)

在其中一条道路上，有一只食蚁兽，当经过该道路的蚁群大小恰好为 $k$ 时，它会把这个蚁群的蚂蚁全部吃掉。

现在请你求出食蚁兽一共吃掉多少只蚂蚁。

inputFormat:
第一行三个整数 $n, g, k$。

之后一行 $g$ 个整数，分别为 $m_1, m_2,\dots, m_g$。

之后 $n-1$ 行，每行两个整数 $a, b$，表示在 $a, b$ 之间有一条边。

输入的第一条边是食蚁兽所在的边。

outputFormat: 输出一行一个整数， 表示所有被吃掉的蚁群的大小之和。


title: [POI2014] TUR-Tourism

description:
King Byteasar believes that Byteotia, a land full of beautiful sights, should attract lots of tourists,    who should spend lots of money, which should eventually find their way to the royal treasury.

But reality does not live up to his dream.

So the king instructed his councilor to look into this issue.

The councilor found out that foreigners keep away from Byteotia due to its sparse road network.

Let us remark that there are $n$ towns in Byteotia, connected by $m$ two way roads, each road linking two different towns.

The roads may lead through picturesque overflies and somewhat less picturesque tunnels.

There is no guarantee that every town can be reached from every other town.

The councilor observed that the current road network does not allow for a long journey.

Namely, wherever one starts the journey, it is impossible to visit more than 10 towns without passing through some town twice.

Due to limited funds in the treasury, no new roads will be constructed at the time.

Instead, Byteasar has decided to build a network of tourist information points (TIPs),    staffed by officers who are to advertise the short trips that are available.

For each town, there should be a TIP either in this town or one of the towns directly    linked by a road.

Moreover, the cost of building the TIP is known for each town.

Help the king by finding the cheapest way of building TIPs that will satisfy aforementioned condition.

inputFormat:
The first line of the standard input contains two integers $n$, $m$ ($2\le n\le 20\ 000$ ,$0\le m\le 25\ 000$), separated by a single space,    that specify the number of towns and roads in Byteotia respectively.

The towns are numbered from $1$ to $n$.

The second line of input contains $n$ integers $c_1,c_2,\cdots,c_n$ ($0\le c_i\le 10\ 000$),    separated by single spaces; the number $c_i$ specifies the cost of building a TIP in the town no. $i$.

Then, a description of the Byteotian road network follows. The $i$-th of the following $m$ lines contains two integers $a_i$,$b_i$ ($1\le a_i<b_i\le n$), separated by a single space, that indicate that the towns no. $a_i$ and $b_i$ are linked by a road. There is at most one (direct) road between any pair of towns.

outputFormat:
Your program should print out one integer to the standard output: the total cost of building all the TIPs.

 ![](https://cdn.luogu.com.cn/upload/pic/6974.png)

translation: 给定一个 $n$ 个点，$m$ 条边的无向图，其中你在第 $i$ 个点建立旅游站点的费用为 $C_i$。在这张图中，任意两点间不存在节点数超过 $10$ 的简单路径。请找到一种费用最小的建立旅游站点的方案，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。


title: [POI2014] LAM-Solar lamps

description:
Byteasar has a large and pretty garden.

As he would like to be able to appreciate its beauty even after dusk,he installed lamps across the garden.

The lamps are directional, i.e., they illuminate only a certain angle, common to them all.

Moreover, Byteasar has aligned them so that they all face the same direction.

Last but not least, these are solar lamps, i.e., they come with solar panelsbut no batteries, strangely enough!  You might think the panels are thus useless,and each lamp will require electricity at night, but not quite: A lamp will produce lightif a sufficient number of lamps illuminate it.

By now, Byteasar has even come up with an order he is going supply the lamps with electricity,thus turning them on.

For simplicity, we number the lamps from 1 to $n$ in this order, i.e., the lamp no. $i$ is supplied with electricity at time $i$.  The only thing left for Byteasar (and you, of course!) is tofigure out when exactly each lamp will start emitting light.  Help Byteasar by writing a programthat will determine the answer to this question.

给N盏灯，没盏灯能照到的角度范围是相同的，第i盏灯在第i秒或者被ki盏灯照到后都会亮起，问所有灯都在什么时刻亮起

inputFormat:
The first line of the standard input contains a single integer $n$($1\le n\le 200\ 000$): the number of lamps Byteasar installed.

In the second line of input, there are four integers $X_1,Y_1,X_2,Y_2$ ($-10^9\le X_i,Y_i\le 10^9$, $(X_i,Y_i)\ne(0,0)$), separated by single spaces,that describe the area illuminated by every lamp.

Namely, if there is a lamp located at the point $(x,y)$, then it illuminatesthe area (together with its edge) within the smaller of the two angles formed by tworays that both originate at $(x,y)$ such that the i-th (for $i=1,2$) ray passes through $(x+X_i,y+Y_i)$. This angle is always smaller than 180 degrees.

The $n$ input lines that follow specify the locations of the lamps: the $i$-th such line contains two integers $x_i,y_i$ ($-10^9\le x_i,y_i\le 10^9$) separated by a single space, that indicate that the lamp no.$i$ is located at the point $(x_i,y_i)$. You may assume that no two lamps share their location.

The last line of the input contains $n$ integers $k_1,k_2,\cdots,k_n$ ($1\le k_i\le n$), separated by single spaces, that signify that if the lamp no. i is in the area illuminated by at least $k_i$ other lamps, then it will start emitting light as well.

outputFormat:
Your program should print out to the standard output a single line with $n$ integers $t_1,t_2,\cdots,t_n$, separated by single spaces.

The number $t_i$ should be the time when the lamp no. $i$ starts producing light.


title: [POI2014] PAN-Solar Panels

description: 对于 $n$ 组询问，每组询问给定四个整数 $a,b,c,d$，从区间 $[a,b]$ 和 $[c,d]$ 中任意选取两个整数 $x$ 和 $y$，求 $\gcd(x,y)$ 的最大值是多少。

inputFormat:
第一行一个整数 $n$ 代表询问数。
接下来 $n$ 行每行代表一个询问，四个整数 $a,b,c,d$ 代表两个区间的范围。

outputFormat: $n$ 行每行一个整数代表区间 $[a,b]$ 和 $[c,d]$ 中任意选取两个整数 $x$ 和 $y$，$\gcd(x,y)$ 的最大值。

hint:
### 数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le a \le b \le 10^9$，$1 \le c\le d \le 10^9$。

### 说明

Translated by @一只书虫仔。


title: [POI2014] ZAL-Freight

description:
The train stations in Upper Bytown and Lower Bytown are connected with a single track rail link.

It takes the train $s$ minutes to travel between them in either direction.

However, the trains departing a station have to be spaced at least one minute apart.

Moreover, at all times, all the trains on the rail link have to go in the same direction.

According to the timetable at our disposal, $n$ cargo trains destined for Lower Bytown are to pass  through the Upper Bytown.  They are to be loaded with goods in Lower Bytown and then return to  Upper Bytown.  For simplicity, we assume that loading the goods on the train takes virtually no time.

We are to determine the minimum possible time of the last train returning to Upper Bytown.

有两个城镇，从A到B需要的时间为S，然后有N辆列车需要从A到B再回来，任何时刻铁路上只能有向着同一个方向前进的列车，然后每辆列车有一个从A出发的最早出站时间，问所有列车全部回到A站的最早时间

inputFormat:
The first line of the standard input contains two integers $n$, $s$($1\le n\le 1\ 000\ 000$, $1\le s\le 10^9$),    separated by a single space, that specify the number of trains and the one-way travel time respectively.

The second line contains $n$ integers $t_1,t_2,\cdots,t_n$ ($0\le t_1\le t_2\le\cdots\le t_n\le 10^9$),separated by a single space, that specify the arrival times of successive trains at the Upper Bytown station.

outputFormat:
Your program should print out a single line with a single integer to the standard output:

the minimum possible time of the last train returning to Upper Bytown.

translation:
Upper Bytown和Lower Bytown的火车站通过一条轨道铁路连接。

沿任何一个方向在它们之间行驶都需要s分钟。

但是，离开车站的火车必须至少间隔一分钟。

而且，在任何时候，铁路上的所有列车都必须朝同一方向行驶。

根据我们的时间表，前往下拜镇的n列货运列车将通过上拜镇。 他们将在下拜敦装载货物，然后返回上拜敦。 为简单起见，我们假设将货物装载到火车上几乎不需要时间。

我们将确定最后一班火车返回Upper Bytown的最短时间。

**两个车站发车都必须至少间隔一分钟。**


title: [POI2015] CZA

description: $n$ 个人（编号为 $1 \sim n$）围着圆桌坐成一圈。座位相邻的两个人，其编号之差的绝对值不可以超过 $p$。他们之中有些人不喜欢别人。如果 $a$ 不喜欢 $b$，那么 $b$ 不能坐在 $a$ 右边的那一个位置上。现在，假设第 $n$ 个人的座位已经固定，要给剩下的人安排座位，共有几种合法方案？

inputFormat: 第一行包含三个整数 $n,k,p$（$1\le n\le {10}^6$，$0\le k\le {10}^5$，$0\le p\le 3$）。接下来 $k$ 行，每行含两个整数 $a_i, b_i$（$1\le a_i, b_i \le n$，$a_i \neq b_i$），表示 $a_i$ 不喜欢 $b_i$。同一组 $a_i,b_i$ 不会重复输入。

outputFormat: 输出一个整数，表示方案数模 ${10}^9+7$ 后的值。

hint: 原题名称：Czarnoksiężnicy okrągłego stołu。


title: [POI2015] KIN

description:
共有 $m$ 部电影，编号为 $1,2,\ldots,m$，第 $i$ 部电影的好看值为 $w_i$。

在 $n$ 天之中，每天会放映一部电影，第 $i$ 天放映的是第 $f_i$ 部。

你可以选择 $l,r$（$1\le l\le r\le n$），并观看第 $l,l+1,\ldots,r$ 天内所有的电影。

但如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。

现在，您需要最大化观看且仅观看过一次的电影的好看值的总和。

inputFormat:
第一行两个整数 $n,m$。

第二行包含 $n$ 个整数，第 $i$ 个表示 $f_i$。

第三行包含 $m$ 个整数，第 $i$ 个表示 $w_i$。

outputFormat: 一行一个整数，表示仅观看过一次的电影的好看值的总和的最大值。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$1\le m\le n\le 10^6$，$1\le f_i\le m$，$1\le w_i\le 10^6$。

----

原题名称：Kinoman。


title: [POI2015] KWA

description:
考虑将正整数 $n$ 拆分成几个不同的平方数之和，比如 $30 = 1^2 + 2^2 + 5^2 = 1^2 + 2^2 + 3^2 + 4^2$，而 $8$ 不存在这样的拆分。

用 $k(n)$ 表示 $n$ 的拆分中，最大的底数最小可能是多少。如果 $n$ 不存在这样的拆分，则令 $k(n) = \infty$。例如：$k(1) = 1$，$k(8) = \infty$，$k(378) = 12$，$k(380) = 10$。

定义一个数 $x$ 被称为“超重”的，当且仅当存在 $y > x$，使得 $k(y) < k(x)$。从上面的例子可知，$378$ 是一个“超重”的数。

给定 $n$，你需要：

1. 求出 $k(n)$。
2. 求出 $1 \sim n$ 中有几个“超重”的数。

inputFormat: 输入仅一行，包含一个正整数 $n$。

outputFormat: 输出一行包含两个整数，分别为对上述两个问题的答案。如果 $k(n) = \infty$，则输出一个减号 `-` 代替。

hint:
**【数据范围】**

对于 $100 \%$ 的数据，$1 \le n \le {10}^{18}$。

----

原题名称：Kwadraty。


title: [POI2015] LAS

description: 圆桌上摆放着 $n$ 份食物，围成一圈，第 $i$ 份食物所含热量为 $c_i$。相邻两份食物之间坐着一个人，共有 $n$ 个人。每个人有两种选择，吃自己左边或者右边的食物。如果两个人选择了同一份食物，这两个人会平分这份食物，每人获得一半的热量。 假如某个人改变自己的选择后（其他 $n-1$ 个人的选择不变），可以使自己获得比原先更多的热量，那么这个人会不满意。请你给每个人指定应该吃哪一份食物，使得所有人都能够满意。

inputFormat:
第一行一个整数 $n$，表示食物的数量（即人数，食物和人都从 $1\sim n$ 编号）。
第二行包含 $n$ 个整数 $c_1,c_2,\dots,c_n$。这里约定，第 $i$（$1\le i<n$）个人左边是第 $i$ 份食物，右边是第 $i+1$ 份食物；而第 $n$ 个人左边是第 $n$ 份食物，右边是第 $1$ 份食物。

outputFormat:
如果不存在这样的方案，仅输出一行 `NIE`。
如果存在这样的方案，输出一行共 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个人选择的食物的编号。如果有多组这样的方案，输出任意一个即可。

hint:
**【数据范围】**

对于所有数据，$2\leqslant n\leqslant 10^6$，$1\leqslant c_i\leqslant 10^9$。

----

原题名称：Łasuchy

感谢 @KSkun 为本题提供 SPJ。


title: [POI2015] PIE

description:
一张 $n\times m$ 的方格纸，有些格子需要印成黑色，剩下的格子需要保留白色。

你有一个 $a\times b$ 的印章，有些格子是凸起（会沾上墨水）的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求：

1. 印章不可以旋转。
2. 不能把墨水印到纸外面。
3. 纸上的同一个格子不可以印多次。

inputFormat:
第一行一个整数 $q$（$1\leq q\leq 10$），表示测试点数量。

接下来 $q$ 个测试点，每个测试点中：

第一行包含 $4$ 个整数 $n,m,a,b$（$1\leq n,m,a,b\leq 10^3$）。

接下来 $n$ 行，每行 $m$ 个字符，描述纸上的图案。`.` 表示留白，`x` 表示需要染黑。

接下来 $a$ 行，每行 $b$ 个字符，描述印章。`.` 表示不沾墨水，`x` 表示沾墨水。

outputFormat: 对于每个测试点，输出 `TAK`（是）或 `NIE`（否）。


title: [POI2015] LOG

description:
维护一个长度为 $n$ 的序列，一开始都是 $0$，支持以下两种操作：

1. `U k a` 将序列中第 $k$ 个数修改为 $a$。
2. `Z c s` 在这个序列上，每次选出 $c$ 个正数，并将它们都减去 $1$，询问能否进行 $s$ 次操作。

每次询问独立，即每次询问不会对序列进行修改。

inputFormat:
第一行包含两个正整数 $n,m$，分别表示序列长度和操作次数。

接下来 $m$ 行为 $m$ 个操作。

outputFormat: 包含若干行，对于每个 `Z` 询问，若可行，输出 `TAK`，否则输出 `NIE`。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6$，$1\leq k,c\leq n$，$0\leq a\leq 10^9$，$1\leq s\leq 10^9$。

----

原题名称：Logistyka。


title: [POI2015] POD

description:
长度为 $n$ 的一串项链，每颗珠子是 $k$ 种颜色之一。第 $i$ 颗与第 $i-1,i+1$ 颗珠子相邻，第 $n$ 颗与第 $1$ 颗也相邻。

切两刀，把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。

求方案数量（保证至少存在一种），以及切成的两段长度之差绝对值的最小值。

inputFormat:
第一行 $n,k$（$2\leq k\leq n\leq 10^6$）。颜色从 $1$ 到 $k$ 标号。

接下来 $n$ 个数，按顺序表示每颗珠子的颜色。（保证 $k$ 种颜色各出现至少一次）。

outputFormat: 一行两个整数：方案数量，和长度差的最小值。

hint:
**【样例解释】**

四种方法中较短的一条分别是 $(5),(4),(1,1),(4,1,1)$。相差最小值 $6-3=3$。

----

原题名称：Podział naszyjnika。


title: [POI2015] PUS

description:
给定一个长度为 $n$ 的正整数序列 $a$，每个数都在 $1$ 到 $10^9$ 范围内，告诉你其中 $s$ 个数，并给出 $m$ 条信息，每条信息包含三个数 $l,r,k$ 以及接下来 $k$ 个正整数，表示 $a_l, a_{l+1}, \ldots, a_{r-1}, a_r$ 里这 $k$ 个数中的任意一个都比任意一个剩下的 $r-l+1-k$ 个数大（严格大于，即没有等号）。

请任意构造出一组满足条件的方案，或者判断无解。

inputFormat:
第一行包含三个正整数 $n,s,m$（$1 \leq s \leq n  \leq 10^5$，$1 \leq m \leq 2 \times 10^5$）。接下来 $s$ 行，每行包含两个正整数 $p_i,d_i$,表示已知 $a_{p_i}=d_i$，保证 $p_i$ 递增。

接下来 $m$ 行,每行一开始为三个正整数 $l_i,r_i,k_i$）$1 \leq l_i < r_i \leq n$，$1 \leq k_i \leq r_i-l_i$），接下来 $k_i$ 个正整数 $x_1..x_2...x_{k_i}$（$l_i \leq x_1 < x_2 < ... < x_{k_i} \leq r_i$），表示这 $k_i$ 个数中的任意一个都比任意一个剩下的 $r_i-l_i+1-k_i$ 个数大。（$\sum k \leq 3 \times 10^5$）

outputFormat: 若无解，则输出 `NIE`。否则第一行输出 `TAK`，第二行输出 $n$ 个正整数，依次输出序列 $a$ 中每个数。

hint:
原题名称：Pustynia。

本题另外提供两组额外样例，可以在附件中下载。


title: [POI2015] KUR

description:
给定 $n,a,b,p$，其中 $n,a$ 互质。

定义一个长度为 $n$ 的 01 串 $c_0c_1\cdots c_{n-1}$，其中 $c_i$ 等于 0 当且仅当 $(ai+b) \bmod n < p$。

给定一个长为 $m$ 的小 01 串，求出小串在大串中出现了几次。

inputFormat:
第一行包含整数 $n,a,b,p,m$（$2\leq n\leq 10^9$，$1\le p,a,b,m<n$，$1\le m\le 10^6$）。保证 $n$ 和 $a$ 互质。

第二行一个长度为 $m$ 的 01 串。

outputFormat: 一个整数，表示小串在大串中出现了几次。

hint:
**【样例解释】**

![](https://cdn.luogu.com.cn/upload/image_hosting/qd6imu53.png)

----

原题名称：Kurs szybkiego czytania


title: [POI2015] TRZ

description: 给定一个长度为 $n$ 的仅包含 $\texttt B$、$\texttt C$、$\texttt S$ 三种字符的字符串，请找到最长的一段连续子串，使得这一段要么只有一种字符，要么有多种字符，但是没有任意两种字符出现次数相同。

inputFormat:
第一行包含一个正整数 $n$（$1\leq n\leq 10^6$），表示字符串的长度。

第二行一个长度为 $n$ 的字符串。

outputFormat: 包含一行一个正整数，即最长的满足条件的子串的长度。

hint:
**【样例解释】**

选择 $\texttt {BSSBCS}$ 这个子串。

----

原题名称：Trzy wieże。


title: [POI2015] ODW

description:
给定一棵 $n$ 个点的树，树上每条边的长度都为 $1$，第 $i$ 个点的权值为 $a_i$。

Byteasar 想要走遍这整棵树，他会按照某个 $1$ 到 $n$ 的全排列 $b$ 走 $n-1$ 次，第 $i$ 次他会从 $b_i$ 点走到 $b_{i + 1}$ 点，并且这一次的步伐大小为 $c_i$。

对于一次行走，假设起点为 $x$，终点为 $y$，步伐为 $k$，那么Byteasar会从 $x$ 开始，每步往前走 $k$ 条边，数据保证了每次行走的距离是 $k$ 的倍数。

请帮助 Byteasar 统计出每一次行走时经过的所有点的权值和。

inputFormat:
第一行包含一个正整数 $n$（$2 \le n \le 50000$）。表示节点的个数。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $a_i$（$1 \le a_i \le 10000$），分别表示每个点的权值。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$（$1 \le u,v \le n$），表示 $u$ 与 $v$ 之间有一条边。

接下来一行包含 $n$ 个互不相同的正整数，其中第 $i$ 个数为 $b_i$（$1 \le b_i \le n$），表示行走路线。

接下来一行包含 $n-1$ 个正整数，其中第 $i$ 个数为 $c_i$（$1 \le c_i < n$），表示每次行走的步伐大小。

outputFormat: 包含 $n-1$ 行，每行一个正整数，依次输出每次行走时经过的所有点的权值和。

hint: 原题名称：Odwiedziny。


title: [POI2015] MYJ

description: 有 $n$ 家洗车店从左往右排成一排，每家店都有一个正整数价格 $p_i$。有 $m$ 个人要来消费，第 $i$ 个人会驶过第 $a_i$ 个开始一直到第 $b_i$ 个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于 $c_i$，那么这个人就不洗车了。请给每家店指定一个价格，使得所有人花的钱的总和最大。

inputFormat: 第一行包含两个正整数 $n,m$（$1 \le n \le 50$，$1 \le m \le 4000$）。接下来 $m$ 行，每行包含三个正整数 $a_i,b_i,c_i$（$1 \le a_i \le b_i \le n$，$1 \le c_i \le 5\times 10^5$）。

outputFormat: 第一行输出一个正整数，即消费总额的最大值。第二行输出 $n$ 个正整数，依次表示每家洗车店的价格 $p_i$，要求 $1 \le p_i \le 5\times 10^5$。若有多组最优解，输出任意一组。

hint: 原题名称：Myjnie。


title: [POI2015] WIL

description: 给定一个长度为 $n$ 的序列，你有一次机会选中一段连续的长度不超过 $d$ 的区间，将里面所有数字全部修改为 $0$。请找到最长的一段连续区间，使得该区间内所有数字之和不超过 $p$。

inputFormat:
输入的第一行包含三个整数，分别代表 $n,p,d$。

第二行包含 $n$ 个整数，第 $i$ 个整数代表序列中第 $i$ 个数 $w_i$。

outputFormat: 包含一行一个整数，即修改后能找到的最长的符合条件的区间的长度。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$1 \le d \le n \le 2 \times 10^6$，$0 \le p \le 10^{16}$，$1 \leq w_i \leq 10^9$。

----

原题名称：Wilcze doły。


title: [POI2015] MOD

description: 给定一棵无根树，边权都是 $1$，请去掉一条边并加上一条新边，定义直径为最远的两个点的距离，请输出所有可能的新树的直径的最小值和最大值。

inputFormat:
第一行包含一个正整数 $n$，表示这棵树的点数。
接下来 $n-1$ 行，每行包含两个正整数，表示 $u,v$ 之间有一条边。

outputFormat:
第一行输出五个正整数 $k,x_1,y_1,x_2,y_2$，其中 $k$表示新树直径的最小值，$x_1,y_1$ 表示这种情况下要去掉的边的两端点，$x_2,y_2$ 表示这种情况下要加上的边的两端点。

第二行输出五个正整数 $k,x_1,y_1,x_2,y_2$，其中 $k$ 表示新树直径的最大值，$x_1,y_1$ 表示这种情况下要去掉的边的两端点，$x_2,y_2$ 表示这种情况下要加上的边的两端点。若有多组最优解，输出任意一组。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$2 \le n \le 5 \times 10 ^ 5$。

----

原题名称：Modernizacja autostrady。

感谢 @cn：苏卿念 提供 spj


title: [POI2015] WYC

description:
给定一张 $n$ 个点 $m$ 条边的带权有向图，每条边的边权只可能是 $1$，$2$，$3$ 中的一种。

将所有可能的路径按路径长度排序，请输出第 $k$ 小的路径的长度，注意路径不一定是简单路径，即可以重复走同一个点。

inputFormat:
第一行包含三个整数 $n,m,k$（$1\le n\le 40$，$1\le m\le 1000$，$1\le k\le 10^{18}$）。

接下来 $m$ 行，每行三个整数 $u,v,c$（$1\leq u,v\leq n$，$u\neq v$，$1\le c\le 3$），表示从 $u$ 出发有一条到 $v$ 的单向边，边长为 $c$。

**可能有重边**。

outputFormat: 包含一行一个正整数，即第 $k$ 短的路径的长度，如果不存在，输出 $-1$。

hint:
**【样例解释】**

长度为 $1$ 的路径有 $1\to 2$，$5\to 3$，$4\to 5$。长度为 $2$ 的路径有 $2\to3$，$3\to4$，$4\to5\to3$。长度为 $3$ 的路径有 $4\to6$，$1\to2\to3$，$3\to4\to5$，$5\to3\to4$。长度为 $4$ 的路径有 $5\to3\to4\to5$。

----

原题名称：Wycieczki。


title: 数列游戏

background:
此题为改编题，特别鸣谢倪星宇同学。

有一次，HKE和LJC在玩一个游戏。

description:
游戏的规则是这样的：LJC在纸上写下两个长度均为N的数列A和B，两个数列一一对应。HKE每次可以找两个相邻的数A[i]和A[i+1]，如果它们两个不互质，HKE可以选择得到(B[i]+B[i+1])分，然后擦掉A和B位置上的第i,i+1个数，并把两个序列重新按顺序编号。当所有相邻的数互质时，游戏结束。

HKE想知道他最大得分是多少。

inputFormat:
第1 行一个整数N；

第2 行N 个整数，依次表示Ai；

第3 行N 个整数，依次表示Bi。

outputFormat: 仅含一个整数，表示B 列被删去的可能最大和。

hint:
对于30%的数据，N ≤ 20；

对于60%的数据，N ≤ 100；

对于80%的数据，N ≤ 500

对于100%的数据，N ≤ 800, 1 ≤ Ai, Bi ≤ 10^9。


title: Koishi Loves Number Theory

description:
Koishi 十分喜欢数论。

她的朋友 Flandre 为了检测她和数论是不是真爱，给了她一个问题。

已知 $f(n)=\sum_{i=0}^nx^i$

给定 $x$ 和 $N$ 个数 $a_i$，求 $\mathrm{lcm}(f(a_1),f(a_2),...,f(a_N))$ 对 $10^9+7$ 取模。

按照套路，呆萌的 Koishi 当然假装不会做了，于是她来向你请教这个问题，希望你能在 $1$ 秒内给她答案。

inputFormat: 第一行包含两个整数 $x$ 和 $N$，接下来一行 $N$ 个整数表示 $a_i$。

outputFormat: 一个整数，表示答案。

hint:
$\mathrm{lcm}$ 表示若干个数的**最小公倍数**。

对于 $10\%$ 的数据，$1\leq N\leq 100$，$0\leq a_i\leq 9$，$x=2$。

对于另外 $20\%$ 的数据，$1\leq N\leq 50$，$0\leq a_i\leq 100$，$2\leq x\leq 10$。

对于另外 $30\%$ 的数据，$1\leq N\leq 16$，$0\leq a_i\leq 10^9$，$2\leq x\leq 10^{18}$。

对于 $100\%$ 的数据，$1\leq N\leq 100$，$0\leq a_i\leq 10^9$，$2\leq x\leq 10^{18}$，且 $x\not\equiv 1\pmod{10^9+7}$。


title: Koishi Loves Construction

description:
Koishi 决定走出幻想乡成为数学大师！

Flandre 听说她数学学的很好，就给 Koishi 出了这样一道构造题：

Task1：试判断能否构造并构造一个长度为 $n$ 的 $1 \dots n$ 的排列，满足其 $n$ 个前缀和在模 $n$ 的意义下互不相同。

Task2：试判断能否构造并构造一个长度为 $n$ 的 $1 \dots n$ 的排列，满足其 $n$ 个前缀积在模 $n$ 的意义下互不相同。

按照套路，Koishi 假装自己根本不会捉，就来找你帮忙辣。

inputFormat:
第一行两个整数 $X$ 和 $T$，分别表示 Task 类型和测试点内的数据组数。

接下来 $T$ 行，每行一个整数表示每组数据中的 $n$。

outputFormat:
为了方便 SPJ 的编写，您需要**遵从以下格式**输出。

对于每组数据仅包含**一行**输出：

1. 如果您认为当前数据不存在符合题意的构造，只需输出一个整数 $0$。
2. 如果您认为当前数据存在符合题意的构造却不会构造，只需输出一个整数 $1$。
3.  如果您认为当前数据存在符合题意的构造并成功构造，则需要先输出一个整数 $2$，再输出 $n$ 个整数表示构造的方案。

**每两个整数之间需要有空格作为分隔符**。

hint:
对于每组数据：

1. 如果您对于构造的存在性判断正确，您将会得到 $30\%$ 的分数，若您的构造符合题意或者确实不存在符合题意的构造，您将会得到剩余的 $70\%$ 的分数。
2. 如果您对于构造的存在性判断不正确，您将不会得到任何分数。

对于每组测试点，您的得分将是本组数据点中得分的最小值。

测试点类型 $1$：$10$ 分，满足 $X = 1$，$1 \leq n \leq 10$。
测试点类型 $2$：$40$ 分，满足 $X = 1$，$1 \leq n \leq {10}^5$。
测试点类型 $3$：$10$ 分，满足 $X = 2$，$1 \leq n \leq 10$。
测试点类型 $4$：$40$ 分，满足 $X = 2$，$1 \leq n \leq {10}^5$。

对于所有测试点，满足 $1 \leq T \leq 10$。


title: 随机数生成器

description:
sol 研发了一个神奇的随机数系统，可以自动按照环境噪音生成真·随机数。

现在 sol 打算生成 $n$ 个 $[1,x]$ 的整数 $a_1, ..., a_n$，然后进行一些询问。

$q$ 次询问，每次询问 $i$ 有两个参数 $l_i$ 和 $r_i$，sol 会计算 $\min_{l_i \leq j \leq r_i} a_j$（$a$ 数组中下标在 $l_i, r_i$ 之间的数的最小值）。

最后测试结果会是这些询问得到的结果的最大值。

sol 进行了很多次实验，现在他想问问你测试结果的期望大小是多少，对 $666623333$ 取模。

inputFormat:
第一行三个数 $n, x, q$。

下面 $q$ 行，第 $i$ 行两个数表示 $l_i$ 和 $r_i$。

outputFormat: 一行一个数，表示答案。


title: 签到题

background:
这是一道签到题！

**建议做题之前仔细阅读数据范围！**

description:
我们定义一个函数：$\operatorname{qiandao}(x)$ 为小于等于 $x$ 的数中，与 $x$ **不互质**的数的个数。

这题作为签到题，给出 $l$ 和 $r$，求出：

$$\sum_{i=l}^r \operatorname{qiandao}(i)\bmod 666623333$$

inputFormat: 一行两个整数，$l$、$r$。

outputFormat: 一行一个整数表示答案。


title: Koishi Loves Segments

description:
Koishi 喜欢线段。

她的 $n$ 条线段都能表示成数轴上的某个闭区间 $[l,r]$。Koishi 喜欢在把所有线段都放在数轴上，然后数出某些点被多少线段覆盖了。

Flandre 看她和线段玩得很起开心，就抛给她一个问题：

数轴上有 $m$ 个点突然兴奋，如果自己被身上覆盖了超过 $x$ 条线段，这个点就会浑身难受然后把 Koishi 批判一番。

Koishi 十分善良，为了不让数轴上的点浑身难受，也为了让自己开心，她想在数轴上放入尽量多的线段。

按照套路，Koishi 假装自己并不会做这道题，所以她就来求你帮忙。并承诺如果你解决了问题就给你打一通电话。

inputFormat:
第一行两个个整数 $n,m$，分别表示插入的线段数和关键点数。

接下来 $n$ 行，每行两个整数 $l,r(l\leq r)$，表示线段 $[l,r]$ 的端点。

接下来 $m$ 行，每行两个整数 $p,x$，表示有个位于 $p$ 的点突然兴奋，并认为自己身上不得覆盖超过 $x$ 条线段

outputFormat: 一个整数，表示最多能放入的线段数。

hint:
对于 $20\%$ 的数据，满足$1\leq n,m\leq 20$。

对于 $60\%$ 的数据，满足$1\leq n,m\leq 100$。

对于 $80\%$的数据，满足$1\leq n,m\leq 5000$。

对于 $100\%$ 的数据，满足$1\leq x\leq n\leq 2\times 10^5,1\leq m\leq 4\times 10^5,|l|,|r|,|p|\leq 10^7$

如果一个点兴奋了两次，那么 Koishi 应当满足它的**较严苛的要求**（也就是 $p$ 相同时 $x$ 取最小值啦）

请适当使用读入优化。


title: 雪辉

background:
**时间限制3s，空间限制512MB**

三周目的由乃被钦定成为了卡密，她立刻赶去二周目的世界寻找雪辉

但是按照设定，两个平行世界是没法互相影响的，也就是原则上由乃是没法去二周目世界的

这时候Deus又跳出来说，其实设定是作者骗你的，只要爱的力量足够强大什么都可以做到（好狗血）

Deus：由乃你为了雪辉是不是什么都可以做呀

yuno：当然啦这还用想

Deus：那你帮我做个题吧

yuno：只要不是数据结构，什么题我都做

Deus：出题人是那个n????????呀，他出（抄）的题除了傻逼数据结构还有啥。。。

yuno：你说的很有道理。。。

Deus：上次那个题你不是两分钟就秒了吗，这个题比那个还简单

yuno：（小声）其实那个是bzoj上面的大佬帮我做的

Deus：好吧就这么愉快的钦定了

![](https://cdn.luogu.com.cn/upload/pic/4134.png)

description:
给一个n个点的树，点有点权，有m次询问，每次询问多条链的并有多少种不同的点权以及它的mex

mex就是一个集合中最小的没有出现的非负整数，注意0要算

比如说集合是1,9,2,6,0,8,1,7，则出现了0,1,2,6,7,8,9这7种不同的点权，因为没有3所以mex是3

![](https://cdn.luogu.com.cn/upload/pic/4132.png)

inputFormat:
第一行三个数n，m，意义如题所述，和一个数f

如果f是0，代表Deus没有使用膜法，如果f是1，代表Deus使用了膜法

之后一行n个数，表示点权

之后n-1行，每行两个数x，y，表示x和y节点之间有一条边，保证是一个树

之后m行，每行先是一个数a，表示这次输入a条链，紧接着2a个数(x1,y1)(x2,y2)...表示每条树链

如果数据被Deus施了膜法，这2a个数都要异或上上一个询问的答案lastans，如果是第一次询问则这个lastans = 0，因为每次询问有两个答案，lastans为这两个答案的和

如果没有膜法，则-1s并且不异或

outputFormat: m行，每行两个数表示点权种类数以及mex

hint:
设a的和为q

对于20%的数据，n,q<=1000，f=0

对于另外30%的数据，n,q<=100000，树是一条链，f=0

对于所有数据n,q<=100000,且点权<=30000

最后，由乃祝大家新年快乐

![](https://cdn.luogu.com.cn/upload/pic/4135.png)


title: 美好的每一天

background:
**时间限制3s,空间限制162MB**

素晴らしき日々

我们的情人，不过是随便借个名字，用幻想吹出来的肥皂泡，把信拿去吧，你可以使假戏成真。我本来是无病呻吟，漫无目的的吐露爱情---现在这些漂泊不定的鸟儿有地方栖息了，你可以从信里看出来。拿去吧---由于不是出自真心，话就说得格外动听，拿去吧，就这么办吧...

由于世界会在7月20日完结，作为救世主，间宫卓司要在19日让所有人回归天空

现在已经是19日傍晚，大家集合在C栋的天台上，一共n个人

在他们面前，便是终之空，那终结的天空

![](https://cdn.luogu.com.cn/upload/pic/4139.png)

description:
回归天空是一件庄重的事情，所以卓司决定让大家分批次进行，给每个人给了一个小写字母'a'->'z'作为编号

一个区间的人如果满足他们的**编号重排之后可以成为一个回文串**，则他们可以一起回归天空，即这个区间可以回归天空

由于卓司是一个喜欢妄想的人，他妄想了m个区间，每次他想知道每个区间中有多少个子区间可以回归天空

因为世界末日要来了，所以卓司的信徒很多

![](https://cdn.luogu.com.cn/upload/pic/4138.png)

inputFormat:
第一行两个数n,m

之后一行一个长为n的字符串，代表每个人的编号

之后m行每行两个数l,r代表每次卓司妄想的区间

outputFormat: m行，每行一个数表示答案

hint:
对于10%的数据，n,m<=100

对于30%的数据，n,m<=2000

对于100%的数据，n,m<=60000

**字符集大小有梯度**

在大家回归天空之后，彩名露出了阴冷的笑容

![](https://cdn.luogu.com.cn/upload/pic/4137.png)


title: 小清新提交答案题

description:
这是一道提交答案题。

相信大家都玩过黄金矿工这款游戏吧！不过如果没有玩过建议**赛后**再玩。

 ![](https://cdn.luogu.com.cn/upload/pic/4469.png)

这道题与原游戏**有一些不同**，请仔细阅读规则。

将矿区抽象为一个2s\*s的矩形，以左上角作为坐标原点，向右为x轴正方向，向下为y轴正方向，建立平面直角坐标系。

矿工开始在(s,0)，矿工可以在x轴一部分：原点与(2s,0)的连线（线段）上随意移动。

把矿区中的黄金等物品抽象为坐标系中此矩形内一个个不相交的圆，每个圆有一个价值，可正可负。

这里我们将抓取的过程抽象为以矿工为一端射出一条射线，如果不与任何圆相交（相切不算），那么这次抓取是无效的；否则矿工将会抓取到相交的圆中最早碰到的一个（较近的交点与矿工距离最近的一个圆）。

 ![](https://cdn.luogu.com.cn/upload/pic/4470.png)

（**抱歉这幅图上的文字标错了，应为(2s,0)，懒得重画了**）

黄金矿工这款游戏的目的是在规定时间上抓取价值尽量高的物品。

移动与抓取都需要时间，移动1单位距离需要花费k1的时间，将一次有效抓取的距离定义为抓取到的圆与射线较近的交点与矿工的距离，有效抓取每1单位距离需要花费k2的时间（无效抓取将会被忽略）。

你将要操纵这位矿工，给出移动和抓取指令，使得获取的价值尽量大。如果某次操作后你所用的总时间超过了规定时限，这次及以后操作将会被忽略。详细格式可见输出描述。

**由于矿工比较懒，矿工只接受2n次操作（n为圆的个数，无论是否是无效抓取），多余操作将被忽略。**

判定时的eps为$10^{-7}$。若你射出的射线与圆两交点的距离不超过该eps，那么将不会判定为相交。若你的用时与时限的差不超过eps，那么也不会被判定为超过时限。

由于这是提交答案题，我们会提供输入数据、评分参数和checker下载，链接在最后。

inputFormat:
第一行五个数s、t、k1、k2、n，s、k1、k2见题面，t为规定时限，n为圆的个数。

以下n行每行四个数$x_i,y_i,r_i,v_i$，分别表示编号为i的圆圆心x坐标、圆心y坐标、半径和价值。

n、$v_i$一定为整数，其余量可能为实数。

outputFormat:
若干行，表示你的操作。

每行开头一个字符为m或g，然后一个空格。（m=move，g=grab）

如果字符是m，接下来应该接一个实数p，$0 \leq p \leq 2s$，表示将矿工移动到(p,0)。

如果字符是g，接下来应该接一个实数a，$0.2 \leq a \leq 179.8$，表示抓取的射线与x轴正方向夹角为a°。

**这两个实数建议保留10位小数。**

超过时限和超过2n次的操作将被忽略。如果在输出文件中包含不合法信息该点可能会直接被判为0分。

samples:
m 1
g 45
（仅为一种可能输出）

hint:
#### 样例解释

开始矿工在(4,0)，移动到(1,0)，花费3时间。

如图矿工发射出一条射线，抓取到第一个圆，获取到1价值，花费$2\sqrt{2}$时间。

当然这不是花费时间最小的解，存在其他解。

 ![](https://cdn.luogu.com.cn/upload/pic/4318.png)

#### 评分标准

对于每个点，如果你的输出不符合输出格式，得0分。

否则，假设你获得的价值为a，每个点有三个评分参数，标准答案b、一个实数w、一个0或1的整数f。

若$a<0$，你将获得0分。

若$a>b$，你将获得$10+f$分（这意味着部分点你可能会获得11分）。

否则你将获得$\lfloor 10(\frac{a}{b})^w\rfloor$分。（$\lfloor x \rfloor$表示不大于x的最大整数）

#### 如何测试和提交

下载下发文件（见附件），里面有mine1.in~mine10.in、mine1.ans~mine10.ans和checker.cpp、checker\_win32.exe、tester.bat、testlib.h，**in、ans和checker.cpp与洛谷上实际测试使用的完全相同**。windows以外的系统，可以自行编译checker.cpp。

测试时在同一目录下放置mine1.out~mine10.out，对于windows用户，运行tester.bat，会自动调用checker\_win32.exe返回每个点的结果。对于其它系统的用户，手动调用checker mine1.in mine1.out mine1.ans即可返回第一个点的评测结果，其它点同理。

checker会返回形如points 0.9 Your ans is aaa, done bbb attempts, time used ccc, ddd remained的结果，表示这个点你可以获得9分，你得到的价值是aaa，成功进行了开始bbb个操作，用了ccc的时间，剩下ddd的时间。如果剩下的时间为负，表示最后一个（没有成功执行的）操作超时了。

提交时可以直接将mine1.out~mine10.out打包上传，一个一个点输入提交亦可。


title: 小清新数据结构题

description:
在很久很久以前，有一棵n个点的树，每个点有一个点权。

现在有q次操作，每次操作是修改一个点的点权或指定一个点，询问以这个点为根时每棵子树点权和的平方和。

（题目不是很好懂，没看太懂的可以看看样例解释）

inputFormat:
第一行两个整数n、q。

接下来n-1行每行两个整数a和b，表示树中a与b之间有一条边，保证给出的边不会重复。

接下来一行n个整数，第i个整数表示第i个点的点权。

接下来q行每行两或三个数，如果第一个数为1，那么接下来有两个数x和y，表示将第x个点的点权修改为y，如果第一个数为2，那么接下来有一个数x，表示询问以x为根时每棵子树点权和的平方和。

outputFormat: 对于每个询问输出答案。

hint:
##### 样例解释

这是一个菊花图，2与1、3、4间有边。

一开始每个点点权分别为4、3、2、1。

第一个询问以2为根，1、3、4子树中都只有本身一个点，2子树中有所有点，那么1、3、4子树中的点权和就分别是自己的点权4、2、1，2子树中的点权和就是4+3+2+1=10，$4^2+2^2+1^1+10^2=121$。

接下来将第一个点点权修改为3，每个点点权分别为3、3、2、1。

第二个询问以3为根，1、4子树中只有自己，2子树中有1、2、4，3子树中有所有点，1、4子树点权和就是自己的点权3、1，2子树点权和就是3+3+1=7，3子树点权和为3+3+2+1=9，$3^2+1^2+7^2+9^2=140$。

接下来把第二个点点权修改为4，每个点点权分别为3、4、2、1。

第三个询问以4为根，1、3子树点权和就是3和2，2子树点权和就是3+4+2=9，4子树点权和为3+4+2+1=10，$3^2+2^2+9^2+10^2=194$。

##### 数据范围

对于10%的数据，$n,q \leq 2000$。

对于40%的数据，$n,q \leq 60000$。

对于另外30%的数据，保证每次询问的根都为1。

对于100%的数据，$1 \leq n,q \leq 200000$，$-10 \leq$输入的每个点权$\leq 10$。

建议使用输入优化~~，虽然标程没加读入优化也能过~~


title: [Ynoi2017] 由乃的 OJ

description:
由乃正在做她的OJ。现在她在处理OJ上的用户排名问题。

OJ 上注册了 $n$ 个用户，编号为 $1\sim n$，一开始他们按照编号排名。由乃会按照心情对这些用户做以下四种操作，修改用户的排名和编号：然而由乃心情非常不好，因为 Deus 天天问她题。。。

因为 Deus 天天问由乃 OI 题，所以由乃去学习了一下 OI，由于由乃智商挺高，所以 OI 学的特别熟练。

她在 RBOI2016 中以第一名的成绩进入省队，参加了 NOI2016 获得了金牌保送。

Deus：这个题怎么做呀？
yuno：这个不是 NOI2014 的水题吗。。。
Deus：那如果出到树上，多组链询问，带修改呢？
yuno：诶。。。？？？
Deus：这题叫做睡觉困难综合征哟~

虽然由乃 OI 很好，但是她基本上不会 DS，线段树都只会口胡，比如她 NOI2016 的分数就是 $100+100+100+0+100+100$。。。NOIP2017 的分数是 $100+0+100+100+0+100$。

所以她还是只能找你帮她做了。。。

给你一个有 $n$ 个点的树，每个点的包括一个位运算 $opt$ 和一个权值 $x$，位运算有`&`，`|`，`^` 三种，分别用 $1,2,3$ 表示。

每次询问包含三个整数 $x,y,z$，初始选定一个数 $v$。然后 $v$ 依次经过从 $x$ 到 $y$ 的所有节点，每经过一个点 $i$，$v$ 就变成 $v\ opt_i\ x_i$，所以他想问你，最后到 $y$ 时，希望得到的值尽可能大，求最大值。给定的初始值 $v$ 必须是在 $[0,z]$ 之间。

每次修改包含三个整数 $x,y,z$，意思是把 $x$ 点的操作修改为 $y$，数值改为 $z$。

inputFormat:
第一行三个整数 $n,m,k$。$k$ 的意义是每个点上的数，以及询问中的数值 $z$ 都小于 $2^k$。

之后 $n$ 行，每行两个整数 $x,y$ 表示该点的位运算编号以及数值。

之后 $n - 1$ 行，每行两个数 $x,y$ 表示 $x$ 和 $y$ 之间有边相连。

之后 $m$ 行，每行四个数，$Q,x,y,z$ 表示这次操作为 $Q$（$1$ 为询问，$2$ 为修改），$x,y,z$ 意义如题所述。

outputFormat: 对于每个操作 $1$，输出到最后可以得到的最大值。

hint:
Idea：f321dd，Solution：f321dd&nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

对于 $30\%$ 的数据，$n,m\leq 1$。

对于另外 $20\%$ 的数据，$k\leq 5$。

对于另外 $20\%$ 的数据，位运算只会出现一种。

对于 $100\%$ 的数据，$0\leq n,m \leq 10^5$，$0\leq k\leq 64$。


title: 曲面

background: xht喜欢研究数学函数，他特别喜欢反比例函数。

description:
我们知道，反比例函数xy=a的图象是双曲线。

 ![](https://cdn.luogu.com.cn/upload/pic/4375.png)

xht于是想：把它推广到三维是什么样的呢？

定义曲面C(k)为**方程xyz=k所确定的曲面**。

又定义曲面的美观程度P(k)为曲面C(k)上所有**整点**（x,y,z坐标均为整数）到原点的曼哈顿距离的**平方**之和。

（点（x,y,z）到原点的曼哈顿距离为|x|+|y|+|z|）。

现在，xht把一些曲面{C(a),C(a+1)...C(b)}排成一列，你要求出它们美观程度之**和**对10007取模的结果。

inputFormat: 一行两个正整数数a，b


title: 方程组

background:
从小学开始，我们就一直做各种各样的应用题，其中大多数的题目都可以抽象为解方程组。

为了提高效率，省下时间~~打隔膜~~学习OI，xht 准备开发一个自动解题器。其中的一个核心组件就是解方程组的程序，xht 决定将这个任务交给你。

description:
一开始，xht 有 $N$ 个变量，记为 $x_1,x_2,\cdots,x_n$。另有一个常数 $K$，以及 $M$ 个方程，每个方程都形如 $x_a-x_b≡c\pmod K$。

由于题目可能会变化，xht 需要不时增加一个新的方程，或者删掉一个方程。

同时，xht 会给你一些这样的询问：令变量 $x_a=c$，求另一个变量 $x_b \bmod K$ 的值。当然，有的时候会因为条件不足，无法解出 $x_b$，那么就输出 $-1$。

数据保证任意时刻两个变量之间最多存在一个方程。保证不会出现自相矛盾的方程组，也不会出现多余的条件（某个方程可以通过其他一些方程推出来）。

inputFormat:
第一行四个整数 $N,M,K,Q$，含义如上。$Q$ 代表操作的条数。

接下来 $M$ 行，每行三个整数 $a,b,c$，表示方程 $x_a-x_b≡c\pmod K$。

接下来 $Q$ 行，每行第一个数 $t$ 代表操作种类，

\* $t=1$，接下来输入 $a,b,c$，代表增加一条方程 $x_a-x_b≡c\pmod K$；

\* $t=2$，接下来输入 $a,b$，代表删除 $a,b$ 之间的方程，如果这条方程不存在，则什么也不做；

\* $t=3$，接下来输入 $a,b,c$，代表询问：令 $x_a=c$，求 $x_b \bmod K$ 的值；

outputFormat: 对于每一个 $3$ 操作（询问），输出一行一个数 $x$（$0\le x<K$），表示 $x_b \bmod K$，如果条件不足，则输出 $-1$。

hint:
样例的解释：

一开始有两条方程：$x_1-x_2=1$，$x_2-x_3=2$。

第一次询问，令$x_1=0$，解得$x_3=(-3)\bmod100=97$。

第二次询问时，删掉了第二条方程，导致条件不足，无法解出 $x_3$，输出 $-1$。

对于 $40\%$ 的数据，只有询问操作。

对于 $100\%$ 的数据，$1\le M<N\le10^5$，$1\le Q\le10^5$，$2\le K\le10^3$，$1\le a,b\le N$，$0\le c<K$。

保证所有的 $a\ne b$。


title: Bushiroad的偶像派对

background: Bushiroad又叫不许摸。

description:
Bushiroad的派对有N个校园偶像团体，可能来自编号1-N的学校。每个学校可能有多个团体参加，也有可能没有团体参加。在所有的团体都演出完后，进行人气投票。

我们已经掌握了中场时和结束时的两张人气排行表。给出排行表从人气高到低排序，并给出每个组的学校编号（你却不知道具体是哪个团体）

可是，结束时的表是不太准确的。因为基于这样的一个事实：某个团体的结束时的人气不会低于中场的人气，而且每个团体的学校不会改变。结束的表产生一些矛盾。

负责统计的人为了不想背锅，希望尽可能少修改结束时的排行表的某些团体的学校（人气值不能改），使其不矛盾，请问至少要修改多少个呢？

inputFormat:
第一行一个整数N，表示有N个团体。

接下来N行，每行两个整数，$Ta_i, Pa_i$，表示中场时的人气值排行，$Ta_i$表示学校名。$Pa_i$表示人气值，按照人气值高往低排列。

接下来N行，每行两个整数，$Tb_i, Pb_i$，表示结束时的人气值排行。

outputFormat: 一个整数表示答案。

hint:
【数据范围】

对于20%的数据， $N\le16$，时限0.5s。

对于40%的数据， $N\le50$，时限0.5s。

对于70%的数据， $N\le5000$，时限1s。

对于全部测试数据， $N\le200000, A\le10^9$。最后3个点时限3s。


title: 邦邦的大合唱站队

background: BanG Dream!里的所有偶像乐队要一起大合唱，不过在排队上出了一些问题。

description:
N个偶像排成一列，他们来自M个不同的乐队。每个团队至少有一个偶像。

现在要求重新安排队列，使来自同一乐队的偶像连续的站在一起。重新安排的办法是，让若干偶像出列（剩下的偶像不动），然后让出列的偶像一个个归队到原来的空位，归队的位置任意。

请问最少让多少偶像出列？

inputFormat:
第一行2个整数N，M。

接下来N个行，每行一个整数$a_i(1\le a_i \le M)$，表示队列中第i个偶像的团队编号。

outputFormat: 一个整数，表示答案


title: 展翅翱翔之时 (はばたきのとき)

background:
**船が往くよミライへ旅立とう**

**船只启航 朝未来展开旅途**

**青い空笑ってる（なにがしたい?）**

**湛蓝天空露出微笑（想做些什么?）**

**ヒカリになろうミライを照らしたい**

**化作光芒吧 想就此照亮未来**

**輝きは心からあふれ出してもっと先の景色望むんだ**

**光辉自内心满溢而出 愿能望见更加前方的景色**

**Ah!やっと手にしたミライチケットかざして…！**

**Ah!挥舞起终于得手的未来门票…！**

 ![](https://cdn.luogu.com.cn/upload/pic/4529.png)

我们Aqours，终于闪闪发亮了！

2月25和26日，将是我们登上横滨ARENA演唱的日子！

而且，还要在全日本、甚至全世界的好多影院进行转播呢！

转播好像还是通过中继卫星传输的呢！

未来ずら！

description:
不过，好像中继卫星上，出了一些问题呢……

我们的中继卫星一共有 $N$ 颗，编号成 $1$ 到 $N$。不过，好像一个中继卫星可以且仅可以单向地从另一颗中继卫星那儿接收数据。

第 $i$ 颗卫星现在已经被设定到了从第 $A_i$ 颗卫星（称为接收源）那儿接受数据。

不过这些中继卫星的接收源是可以修改的，只不过每次修改要花一定的资金呢。

听说要达成中继的话，这些卫星之间必须**两两之间能够互相（直接或间接）通信**才行啊。

虽然鞠莉家里很有钱，可是这么大的花费，也得提前准备一下呢。

所以，你能帮我们算算这样子一共最少要花多少钱吗？

inputFormat:
第一行一个整数 $N$。

接下来 $N$ 行，每行 $2$ 个整数 $A_i,C_i$，表示初始时，第 $i$ 个中继卫星从第 $A_i$ 颗卫星处接收数据，以及该卫星调整接收源的所需花费。

outputFormat: 输出一个整数，表示鞠莉所需准备的最小的花费。

hint:
### 数据范围及约定

- 对于 $10\%$ 的数据，满足 $N \le 10$。
- 对于 $40\%$ 的数据，满足 $N \le 15$。
- 对于 $70\%$ 的数据，满足 $N \le 3000$。
- 对于 $100\%$ 的数据，满足 $2 \le N \le 100000,1 \le C_i \le 10^9$。

### 以下是彩蛋

事实上 LoveLive 的直播卫星中继只有一颗星，而且永远都是不加密的。

导致只要有一个卫星锅就可以在家偷偷看直播，也就是传说中的卫星源。

lin_toto：万代南梦宫都把浅水湾给买了，居然只有回放，只好跑到香港 the sky 去看 + 手动滑稽。

至于为什么看转播，eplus 表示 LoveLive 系列演唱会的票大家尽管抽选尽管抢，买得到算我输。

于是 lin_toto 在去年 μ's Final LoveLive 的时候拿肉鸡把 eplus 搞趴下了，然后就买到了。

于是今年 eplus 连抢票都不让抢了，全抽选，抽得到算我输。

然后 lin_toto 就去看转播了。


title: 小清新数学题

background:
**本题时限 3s**

友情提示：https://www.luogu.com.cn/problem/P3601

description:
题目还是简单一点好。

我们定义莫比乌斯函数 $\mu(x)$，如果 $x$ 的每个素因子只出现一次，有 $p$ 个素因子，那么 $\mu(x)=(-1)^p$，否则 $\mu(x)=0$。

这题要求你求出 $\sum_{i=l}^r \mu(i)$。

inputFormat: 一行两个整数 $l,r$。


title: 小清新计数题

description:
小 A 正在电脑上玩一个叫做 Truth or Lie 的游戏。

游戏开始时电脑会给出 $n$ 句话，每句话形如“第 $x$ 句话为真”或“第 $x$ 句话为假”，其中 $x$ 是一个 $1$ 到 $n$ 的整数，你只要选择“Good”或者“Bad”，“Good”表示可以决定每句话的真假使每句话的内容都成立，“Bad”反之。

作为一个菜鸡，小 A 只会不停地点“Good”，靠脸过关。

在无数次失败后，非洲人小 A 发现游戏每关中，每句话包含的是“真”还是“假”是固定的，但是每句话中的 $x$ 是在 $1$ 到 $n$ 均匀随机的。

现在小 A 告诉了你某一关每句话的真假，用一个 $01$ 序列表示。第 $i$ 位为 $0$ 表示第 $i$ 句话包含“假”，否则表示包含“真”。现在他想要知道使得点击“Good”正确的方案数。

由于方案数可能比较大，你需要输出方案数对 $998244353$ 取模的结果。

（读不懂题的请移步样例解释）

inputFormat: 一行一个 $01$ 序列，它的长度即为 $n$。

outputFormat: 输出方案数对 $998244353$ 取模的结果。

hint:
### 样例解释

第一句话的内容为“某句话为假”，第二句话的内容为“某句话为真”。所有可能情况如下：

1. 第一句话的内容为“第一句话为假”，第二句话的内容为“第一句话为真”，结果应为 Bad。

2. 第一句话的内容为“第一句话为假”，第二句话的内容为“第二句话为真”，结果应为 Bad。

3. 第一句话的内容为“第二句话为假”，第二句话的内容为“第一句话为真”，结果应为 Bad。

4. 第一句话的内容为“第二句话为假”，第二句话的内容为“第二句话为真”，结果应为 Good，因为只需认为第一句话为假，第二句话为真就符合两句话，所以是 Good。

所以共有一种合法方案。

### 数据范围

- 对于$10\%$ 的数据，$n \leq 7$；
- 对于$20\%$ 的数据，$n \leq 9$；
- 对于$60\%$ 的数据，$n \leq 20$；
- 对于$100\%$ 的数据，$1 \leq n \leq 50$。


title: 相遇问题

background: 此题是相遇问题，小学被奥数冲昏了头脑的慎入2333

description:
Yugo国的城市全在一条直线上，用一条笔直的高速公路连接，有 $n$ 辆机动车在高速往返运动，它们只能在某个城市才能调头，调头不需要时间，机动车不会停。这 $n$ 辆车初始时可能位于不同的城市，在某个时刻同时出发，每辆车每分钟可以到达下一个城市，即每分钟可以动单位 $1$ 的路程。当车到达终点时，它将会消失。给出每辆车的运动轨迹，即车的起点、中途每次调头的点及终点，有 $m$ 次查询，每次查询指定两辆车，问它们一共相遇多少次？

注意：车车相遇点不一定是城市。另外，相遇时其中一辆车到达终点；起始瞬间两辆车位于同一地点不算相遇；其中一辆车正好掉头不算相遇。

inputFormat:
第一行两个整数 $n,m$ ，表示车数和查询的次数。

接下来 $n$ 行，每行的第一个数为$K_i$，表示车的行驶路径包含 $K_i$ 个城市，接下来有 $K_i$ 个数，每个数在区间 $[1,10^7]$ 之间，按顺序表示车运动时经过的城市，包括起点和终点。

所有 $K_i$ 之和不超过 $3\times 10^5$。

接下来 $m$ 行，每行两个整数，表示查询这两辆车一共相遇多少次。

outputFormat: 对每次查询，输出一个整数，表示它们相遇次数。

hint:
对于 $50\%$ 的数据，$n<100,K_i<1000,m<1000$。

对于 $100\%$ 的数据，$2\le K_i \le 3\times 10^5$，$n\le 10^5,m<10^5$ 。

城市的编号在 $[1,10^9]$ 之间。每辆车在路径改变方向的次数不超过 $3\times 10^5$ ；所有车调头的总次数之和不超过 $3\times 10^5$ 。


title: CYaRon!语

background:
「千歌です」（我是千歌）、「曜です」（我是曜）、「ルビィです」（我是露比）、「3人合わせて、We are CYaRon！ よろしくね！」（三人在一起，我们是CYaRon！多多指教哦！）

CYaRon!的三人在学习了编程之后，决定发明一种自己的编程语言，她们称为CYaRon!语。

(ltt: 明明是我帮她们发明的。)

可是，因为洛谷评测机这时候突然爆了，ltt没有时间再帮CYaRon!的三位小姐姐写CYaRon!语的解释器了。

于是ltt就出了这样一道题，然后等着有人交了AC程序就偷走给小姐姐们。

description:
以下是一个典型的CYaRon! 语程序。

```cpp
{ vars
    chika:int
    you:int
    ruby:array[int, 1..2]
    i:int
}
# 以上变量默认值均为0
# 变量名只可是英文字母。

# yosoro语句可以输出一个数字，随后跟一个空格。
:yosoro 2
# 输出2和一个空格(以下不再提到空格)。

# set语句可以为变量赋值。
# 运算符只支持加减号即可。
:set chika, 1
:set you, 2
:yosoro chika + you
# 上一条语句将输出3

# 以下的判断语句均使用以下的格式：
# 操作符，表达式，表达式
# 例如eq, a, 1即C语言中 a==1
# 所有操作符包括: lt: < gt: > le: <= ge: >= eq: == neq: !=

# 日本来的CYaRon三人没法正确地发出if这个音，因此她们就改成了ihu。
{ ihu eq, chika, 1
    :set you, 3
    :yosoro 1
}
# 输出1
# 以上是ihu语句，无需支持else。

# hor语句同理，
# for i=1 to you如下
{ hor i, 1, you
    :yosoro i
}
# 输出1 2 3

# 如下是while和数组的使用方法。
:set i, 1
{ while le, i, 2
    :yosoro i
    :set ruby[i], i+1
    :yosoro ruby[i]
    :set i, i+1
}
# 输出1 2 2 3

# 数组不会出现嵌套，即只会有a[i]、a[i+2]而不会有类似于a[i+b[i]]这样的。

# CYaRon语的最后一行，一定是一个换行。

```

你的任务是写一个CYaRon!语的解释器，实现输入CYaRon!语的程序，解释之执行后输出执行结果。

inputFormat:
输入文件全部为CYaRon!语程序，最后一行保证是个空行。

请处理输入的时候，一直读到EOF为止。

outputFormat:
该CYaRon!语程序的执行结果。

具体上，是该CYaRon!语程序所有:yosoro语句的输出。

samples:
{ vars
    a:int
    b:int
}

:set a, 1
:set b, 2
:yosoro a+b

hint:
对数据做出以下保证：

1. 输入数据一定是合法的CYaRon!语程序，不包含注释，代码、缩进风格 （四个空格）与上述样例相同。**但不保证逗号、运算符前面的空格数量和有无一定相同**。

2. 变量名在10个字符以下，仅包含小写英文，数组最大大小为1000，变量最多50个，所有表达式的运算结果，包括变量的值一定在int范围内。 （但数组可能是类似于[2001..3000]的，下标可能范围为0到1亿）

3. 所有指令小写。

4. 该程序一定能够在合理的时间、内存限制内执行完毕。

5. hor语句执行过程中，循环变量、初始值、结束值不会被循环中的代码改变。

6. **该程序最多500行**

![](https://cdn.luogu.com.cn/upload/pic/4595.png)


title: 妖精大战争

background:
 ![](https://cdn.luogu.com.cn/upload/pic/4726.png)

琪露诺一如既往忙碌地生活着。

某天，在外出时她的家被人破坏了。

损坏的家插着一面奇怪的旗。

旗上画着似曾相识的几个妖精的图案。

狂怒的琪露诺对旗的主人贴出了宣战告示。

就这样，妖精们的大战争开始了。

(摘自《妖精大战争》manual)

description:
三月精Sunny Milk,Lunar Child,Star Sapphire为了让冰之妖精琪露诺加入她们的恶作剧计划，破坏了琪露诺的房子。琪露诺当然不会就此罢休，于是她找到了三月精准备进行复仇，复仇的方式是进行一场弹幕对决。在Normal难度下，Star Sapphire在此次对战中不会出场，因此只有Sunny Milk,Lunar Child两只妖精出场和琪露诺对决了。

在一张符卡中，Sunny Milk和Lunar Child发射的弹幕几乎填满了整个100\*100的正方形战斗场地，并且恰好可以被一条静止不动，非垂直的直线划分成两部分，其中直线上方的部分是Sunny Milk发射的日光弹幕，直线下方的部分是Lunar Child发射的月光弹幕。

琪露诺是最强的妖精，但她面对两只妖精密集的弹幕也会有些紧张。在她的干劲快要被消磨完时，琪露诺忽然发现，如果能用两种不同的策略来对付两种弹幕，获胜的希望将会大大增加。因此，她想知道一些关键的位置会出现什么弹幕。

不幸的是，琪露诺无法判断出分界线在哪里，她只知道当前在战斗场地中每个弹幕的位置，和这个弹幕是月光弹幕还是日光弹幕。在极少情况下(至多0.1%)，琪露诺可能会错误识别弹幕的类型，因为它们实在太像了。琪露诺想要了解的是，对于接下来可能出现弹幕的位置，如果出现了弹幕，它是月光弹幕还是日光弹幕。你能帮帮她吗？

inputFormat:
第一行三个正整数n,m,k。分别表示当前场地上弹幕的数量，和琪露诺想要了解情况的位置的数量，k表示当前是第几个测试点。

接下来n行，每行两个实数x,y和一个整数k,用空格隔开。表示在(x,y)有一个种类为k的弹幕，k=1为日光弹幕，k=-1为月光弹幕。

接下来m行，每行两个实数x,y，表示琪露诺想知道这个位置如果出现弹幕，会出现什么类型的弹幕。

outputFormat:
m行，每行一个整数1或者-1，对应每个询问的结果。

1为日光弹幕，-1为月光弹幕。

hint:
样例解释：

注:该数据因量过小，信息量不足而不合法，可能会发生无法得到准确答案的情况。因此仅供理解题意使用，不可用来测试程序。

观察输入数据，我们发现当y=3时，都是月光弹幕,y=4时，都是日光弹幕。可以猜想直线在y=3~y=4之间。

因此对于四个询问分别回答 1,-1,1,-1

数据范围和提示

单个弹幕的面积可视为0。

若询问的位置恰好落在分界线上，当做在分界线的下方处理。

本题有SpecialJudge。

对于第1个测试点

N=100000,m=100000

若你输出的答案中，正确回答的询问数量大于等于总询问数量的30%，则可以获得该测试点的全部分数,否则得0分。

对于第2~5个测试点，

n=1000，m=1000

若你输出的答案中，正确回答的询问数量大于等于总询问数量的60%，则可以获得该测试点的全部分数,否则得0分。

对于第6~7个测试点，

n=100000，m=100000

若你输出的答案中，正确回答的询问数量大于等于总询问数量的70%，则可以获得该测试点的全部分数,否则得0分。

对于第8~10个测试点，

n=100000，m=100000

若你输出的答案中，正确回答的询问数量大于等于总询问数量的80%，则可以获得该测试点的全部分数,否则得0分。

对于100%的数据

0.000<=x,y<=100.000

所有输入的实数均保留3位小数。

保证输入数据有合法的解能够满足题目要求的判定准确率。

评测时限:对于测试点2~5,时限为1s，其他测试点时限为2s


title: csh和zzy的战争

background:
（背景~~有点~~长，你可以选择读完，也可以选择跳过。）

公元 2040 年，csh 和 zzy 在丑国蛙谷展开了关于非线性配微分方程的正确性与否的相关辩论，史称第四次数学危机。两个人近千页的非人类学术性论文，使整个世界没有其他人听得懂他们在说什么，于是，以 csh 为首的 A 派科学家和以 zzy 为首的 B 派科学家展开了在多次对抗无果之后开始使用武装革命解决，进而引发了全球性的第三次世界大战。作为战争中立派的居润国不想卷入任何一方的斗争，只想喝完手中的咖啡，然而两方元首在多次对抛出橄榄枝无果之后，对居润国提出了一个要求：解决他们在战争中的运送物资问题，当然这个问题早就在 $10^0$ s 内被他们解决，但是居润国却不知道怎么办，而且也不能报上错误的答案，于是就求助了聪明的你们。

description:
现在有 $n$ 个货物发源地，里面是一些待运送的货物。前方有 $m$ 个中转小岛，而你的目的是将所有货物运到战争前沿的军事基地，其运送规则如下：

1. 小岛只能由特定的货物发源地发货，其中只有几个指定的小岛可以向军事基地发货。
2. 小岛与小岛之间有 $e$ 条航道，每条航道上有一个权值 $v$ 代表这条道路开通的代价，而两个小岛之间开通货运的代价 $K$ 是两个小岛之间的最短路径长度。
3. 每个小岛上同时最多不能超过 $w$ 个货物。
4. 每个小岛一次性至多对外运输 $d$ 个货物，小岛对每个目的地至多送货一次。
5. 有 $x$ 个特殊货物发源地（不包含在 $n$ 内）会运送 csh 和 zzy 两个人的一些私人的货物，这些货物会被任何一个小岛无条件接受和送出，即不受 3，4 法则的影响。
6. 整条航路的开发费用为每对小岛开通费用 $K$ 中的最大值 $V$。

请你寻找一个最小的 $V$ 使得所有货物都能按照要求运送到军事基地。

inputFormat:
第一行 $n$，$m$，$x$，$e$，分别表示货物发源地数目，小岛中转站数目，特殊货物发源地数目和航道数目，货物发源地和特殊货物发源地依次标号为 $1$，$2$，$ \dots $，$n+x$。

第二行是 $n+x$ 个数 $a_i$，分别每个货物发源地待发送的货物数量。

第三行是 $m$ 个数，分别表示小岛的限制存货量 $w$。

第四行也是 $m$ 个数，分别表示小岛的限制出货量 $d$。

接下来 $m$ 行，每行开头是一个数 $k$ ，表示有 $k$ 个货物发源地（包括特殊货物发源地）与小岛相连，然后是 $k$ 个数，分别表示货物发源地的编号，最后一个数表示小岛是否与军事基地相连，是则为$1$，否则为$0$。

接下来 $e$ 行，每行是三个数 $u$，$v$，$p$ 表示小岛 $u$，$v$ 之间航道的权值为 $p$。

outputFormat: 一个整数 $V$ ，表示使得所有货物都能按照要求运送到军事基地最小开通费用。

hint:
对于 $100\%$ 的数据， $n \le 3 \times 10^2$，$e \le 10^3$。

几个提示：[https://www.luogu.com.cn/discuss/47710](https://www.luogu.com.cn/discuss/47710)。


title: 小清新签到题

description:
题目还是简单一点好。

给定自然数 $n$、$k$、$x$，你要求出第 $k$ 小的长度为 $n$ 的逆序对对数为 $x$ 的 $1\sim n$ 的排列 $a_1,a_2 ... a_n$ ~~，然后用仙人图上在线分支定界启发式带花树上下界最小费用流解决问题~~，保证存在。

注：逆序对为满足 $i<j$、$a_i>a_j$ 的 $(i,j)$。比较为字典序比较，即比较从前往后第一个不同的位置。第 $k$ 小从 $1$ 开始标号。一个 $1\sim n$ 的排列定义为一个长度为 $n$ 的数列，排序完可以得到 $1\sim n$。

inputFormat: 一行三个自然数 $n$、$k$、$x$。

outputFormat: 输出满足条件的排列，一行n个数，用空格分隔。

hint:
对于 $10\%$ 的数据，$n \leq 8$。

对于 $30\%$ 的数据，$n \leq 10$。

对于 $50\%$ 的数据，$n \leq 50$。

对于另外 $20\%$ 的数据，$k=1$。

对于 $100\%$ 的数据，$1 \leq n \leq 300$，$1 \leq k \leq 10^{13}$，保证存在符合题意的排列。


title: 小清新人渣的本愿

background:
**本题时限3s，空间128MB**

我感觉我要挂省选

人渣的本愿是一个有趣的番

可爱的花火喜欢从小和她谈♂笑♂风♂生的欧♂尼♂酱鸣海，欧尼酱特别想当老师，然后剧本安排当了花火的班主任。

然而有个叫做皆川茜的奇怪的人抢走了欧尼酱！

花火就很失落呀，然后看到一个叫做麦的人也很失落，原来麦喜欢茜老师。。。

花火和麦从此天天谈笑风生，然后决定在一起，把对方当做自己喜欢的人的替代品

因为花火很可爱，所以有许多奇怪的人喜欢花火，比如一个叫做绘鸠早苗的妹子

因为麦长的也不错，所以有许多奇怪的人喜欢麦，比如一个叫做最可的妹子

然后就开始愉快的生♂活了~

以上内容如果你没有看过这个番可以无视掉

按照套路，现在欧尼酱会问花火一个OI问题（一般是数据结构），然后花火肯定不会OI，所以会来请教您这位IOI Au选手，然后您肯定会帮助她

但是
这个套路太无聊了，我们来换一个（但是不会改变您是IOI Au选手的事实）

花火有一天看了几个有趣的番，叫做“在W??身上寻找女装是否搞错了什么”，“从女装开始的?X?”，“我家大佬不可能那么可爱”，然后发现??H太厉害了，然后就穿越到了异世界，和???谈笑风生

花火就和???做了一个交♂易，花火帮???做一道题，然后???帮花火改写地球online的程序，让花火和欧尼酱在♂一♂起

???虽然非常厉害，但是不会数据结构题，他最近刚刚遇到一道有趣的数据结构题，于是他接受了交易

但是花火也不会数据结构题呀

所以又回到了这个老套路，就靠您这个IOI Au选手来帮她了！

以上内容如果你没有看过这个番还是可以无视掉

这里用一个经典的图来解释这个关系（其实没那么蛋疼的）

![](https://cdn.luogu.com.cn/upload/pic/4628.png)

description:
这个题是这样的：

给你一个序列 $a$，长度为 $n$，有 $m$ 次操作，每次询问一个区间是否可以选出两个数它们的差为 $x$，或者询问一个区间是否可以选出两个数它们的和为 $x$，或者询问一个区间是否可以选出两个数它们的乘积为 $x$ ，这三个操作分别为操作 $1,2,3$。

选出的这两个数可以是同一个位置的数。

![](https://cdn.luogu.com.cn/upload/pic/4629.png)

inputFormat:
第一行两个数 $n,m$。

后面一行 $n$ 个数表示 $a_i$。

后面 $m$ 行每行四个数 `opt l r x`。

$opt$ 表示这个是第几种操作，$l,r$ 表示操作的区间，$x$ 表示这次操作的 $x$。

outputFormat: 对于每个询问，如果可以，输出 `hana`，否则输出 `bi`。

hint:
定义 $c$ 为每次的 $x$ 和 $a_i$ 中的最大值，$a_i \geq 0$，每次的 $x\geq 2$。

对于 $10\%$ 的数据，$n,m,c \leq 100$。

对于另外 $10\%$ 的数据，$n,m,c \leq 3\times 10^3$。

对于另外 $10\%$ 的数据，只有 $1$ 操作。

对于另外 $10\%$ 的数据，只有 $2$ 操作。

对于另外 $10\%$ 的数据，只有 $3$ 操作。

对于 $100\%$ 的数据，$n,m,c \leq 10^5$。

![](https://cdn.luogu.com.cn/upload/pic/4630.png)


title: 语言普查

background: Yugo国的人民在进行一次人口普查，由于Yugo国是典型的多民族国家，所以拥有许多种语言。

description:
“Kiaosmaonsnai Assi fi wais

"Kjamqosoaksi mais pas?"

"Oci! Asia olo mnai naso!"

"2333在说什么啊根本听不懂。。。”

这是Yugo国的日常。。。

Yugo国有许多不同的种族，这些不同的种族不同的语言，但是主席扔给了你几本字典，这样，你就知道他们在说什么语了。你的任务就是判断他们在说什么语并填上户口本（？）。

inputFormat:
第一行输入N（1≤N≤100），不同语种的数量。

下一个N行依次包含该语言的名称，后跟该语言中的一个或多个单词，词和词之间用空格隔开。

后面跟一个空行。

之后许多（<1000）行，你需要确定合适的语言。语句是不间断的字符串的大写或小写字母，出现“\" 、"-"或“‘”视为一个单词。没有一个单词会出现在两种或以上语言中。

每行短于256个字符。最多会有1000行的示例文本。

每个示例文本将包含至少一个来自一种语言的单词。示例文本不包含来自多种族语言的单词。示例文本可能包含附加标点符号"." "," "?" "!" ";""("")"、空格和换行，这些符号作为分隔符分隔单词。示例文本可能包含在上面没出现过的单词。

单词匹配不区分大小写。

outputFormat: 输出每行对应的语言。

samples:
4
Qzrian yy ghy qzr
Yugoslavian mihailova petrozavodsk saint-petersburg
Suissvia yugoslavia korse mais kohnin
Mohaian Jzm Wallace Zhangbaohua djh

yy,qzr and ghy are i don't know
mihailova saZk amOmlio
mais c'est pas Ca
wallace is good


title: [SDOI2007] 小组队列

background:
嘛，这道非常简单的给大家提供信心的省选题洛谷居然没有！

这么简单的题怎么可以没有！

给大家提升士气是义不容辞的责任！

所以我就来补一下啦..

值得一提的是，标程是我自己做的..

很渣，因为数据很水所以能 AC..

大神勿喷..

description:
有 $m$ 个小组， $n$ 个元素，每个元素属于且仅属于一个小组。

支持以下操作：

`push x`：使元素 `x` 进队，如果前边有 `x` 所属小组的元素，`x` 会排到自己小组最后一个元素的下一个位置，否则 `x` 排到整个队列最后的位置。

`pop`：出队，弹出队头并输出出队元素，出队的方式和普通队列相同，即排在前边的元素先出队。

inputFormat:
第一行有两个正整数 $n$, $m$，分别表示元素个数和小组个数，元素和小组均从 $0$ 开始编号。

接下来一行 $n$ 个非负整数 $A_i$，表示元素 $i$ 所在的小组。

接下来一行一个正整数 $T$ ，表示操作数。

接下来 $T$ 行，每行为一个操作。

outputFormat: 对于每个出队操作输出一行，为出队的元素。

samples:
4 2
0 0 1 1
6
push 2
push 0
push 3
pop
pop
pop


title: [ZJOI2017] 仙人掌

description:
如果一个**无自环无重边无向连通图**的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

 ![](https://cdn.luogu.com.cn/upload/pic/4742.png)

现在九条可怜手上有一张**无自环无重边的无向连通图**，但是她觉得这张图中的边数太少了，所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图，图中的边数又不能太多。经过权衡，她想要加边后得到的图为一棵仙人掌。

不难发现合法的加边方案有很多，可怜想要知道总共有多少不同的加边方案。

两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。

inputFormat:
多组数据，第一行输入一个整数 $T$ 表示数据组数。

每组数据第一行输入两个整数 $n$,$m$，表示图中的点数与边数。

接下来 m 行，每行两个整数 $u$,$v$(1 ≤ $u$,$v$ ≤ $n$,$u$ ≠ $v$) 表示图中的一条边。保证输入的图联通且没有自环与重边。

outputFormat: 对于每组数据，输出一个整数表示方案数，当然方案数可能很大，请对 998244353 取模后输出。

hint:
**样例说明**

对于第一组样例合法加边的方案有 {},{(2,3)}，共 2 种。

**时空限制**

时间限制1s，空间限制512M。

**数据范围**

![](https://cdn.luogu.com.cn/upload/pic/4743.png)


title: [ZJOI2017] 树状数组

description:
漆黑的晚上，九条可怜躺在床上辗转反侧。难以入眠的她想起了若干年前她的一次悲惨的 OI 比赛经历。那是一道基础的树状数组题。

给出一个长度为 $n$ 的数组 $A$，初始值都为 $0$，接下来进行 $m$ 次操作，操作有两种：

* $1\ x$，表示将 $A_x$  变成 $(A_x + 1) \bmod 2$。
* $2\ l\ r$，表示询问 $(\sum_{i=l}^r A_i) \bmod 2$。

尽管那个时候的可怜非常的 simple，但是她还是发现这题可以用树状数组做。当时非常 young 的她写了如下的算法：

![](https://cdn.luogu.com.cn/upload/pic/4744.png)

其中 $\mathrm{lowbit}(x)$ 表示数字 $x$ **最低**的非 $0$ 二进制位，例如 $\text{lowbit}(5) = 1, \text{lowbit}(12) = 4$。进行第一类操作的时候就调用 $\mathrm{Add}(x)$，第二类操作的时候答案就是 $\mathrm{Query}(l, r)$。

如果你对树状数组比较熟悉，不难发现可怜把树状数组写错了：**$\text{Add}$ 和 $\text{Find}$ 中 $x$  变化的方向反了**。因此这个程序在最终测试时华丽的爆 0 了。

然而奇怪的是，在当时，这个程序通过了出题人给出的大样例——这也是可怜没有进行对拍的原因。

现在，可怜想要算一下，这个程序回答对每一个询问的概率是多少，这样她就可以再次的感受到自己是一个多么非的人了。然而时间已经过去了很多年，即使是可怜也没有办法完全回忆起当时的大样例。幸运的是，她回忆起了大部分内容，唯一遗忘的是每一次第一类操作的 $x$ 的值，因此她假定这次操作的 $x$ 是在 $[l_i, r_i]$  范围内**等概率随机**的。

具体来说，可怜给出了一个长度为 $n$ 的数组 $A$，初始为 $0$，接下来进行了 $m$ 次操作：

* $1\ l\ r$，表示在区间 $[l, r]$ 中等概率选取一个 $x$ 并执行 $\text{Add}(x)$ 。

* $2\ l\ r$，表示询问执行 $\text{Query}(l, r)$ 得到的结果是正确的概率是多少。

inputFormat:
第一行输入两个整数 $n,m$。

接下来 $m$ 行每行描述一个操作，格式如题目中所示。

outputFormat: 对于每组询问，输出一个整数表示答案。如果答案化为最简分数后形如 $\frac x y$，那么你只需要输出 $x\times y^{-1} \bmod 998244353$ 后的值（即输出答案模 $998244353$）。


title: [ZJOI2017] 多项式

description:
九条可怜最近研究了一下多项式在系数模 2 意义下的性质。她发现可以用多项式在模 2 意义下的乘法得到一个很长的字符串：

对于一个 $n$ 次的系数为 0 或 1 的多项式 $f\left ( x \right )$，我们在模 2 意义下计算 $g\left ( x \right ) = f\left ( x \right )^{m}$，则

$g\left ( x \right )$ 为一个 $nm$ 次的多项式，它有 $nm + 1$ 个系数，将这些系数从**高位到低位**写下来，就可以得到一个长度为 $nm + 1$ 的 01 字符串。

例如对于多项式 $f\left ( x \right ) = x^{3} + x + 1$，计算 $g\left( x \right ) = f\left( x \right)^{3} = x^{9} + x^{7} + x^{6} + x^{5} + x^{2} + x^{1} + 1 $，这样我们得到了一个长度为 10 的字符串 1011100111。

现在可怜有一个次数为 $n$ 的多项式 $f\left( x \right )$，整数 $m$, $L$, $R$ 以及一个长度为 $K$ 的 01 串 $t$。令 $s$为 $f\left( x \right )^{m}$得到的字符串， $s\left[L, R\right]$ 为 $s$ 的第 $L$ 个字符到第 $R$ 个字符，可怜想要知道 $t$ 在 $s\left[L, R\right]$中出现了多少次。

inputFormat:
第一行输入一个整数 T 表示数据组数。

每组数据第一行输入五个整数 $n, m, K, L, R$。

第二行输入一个长度为 $n + 1$ 的 01 串表示多项式 $f\left( x \right )$ 的系数，其中第 $i$ 位表示 $f\left( x \right )$ 的第 $n − i + 1$ 次系数。

第三行输入一个长度为 $K$ 的字符串表示字符串 $t$。

outputFormat: 对于每组数据输出一个整数表示答案。

hint:
**时空限制**

时间限制3s，空间限制512M

**数据范围**

![](https://cdn.luogu.com.cn/upload/pic/4746.png)


title: 少女与战车

background:
如果你对山口丁和 G&P 没有兴趣，可以无视题目背景，因为你估计看不懂 ……

 ![](https://cdn.luogu.com.cn/upload/pic/4760.png)

在第 63 回战车道全国高中生大赛中，军神西住美穗带领大洗女子学院的大家打败了其他所有高中，取得了胜利，当然也就不用废校了。

然而一群战车道的领导表示他们是口胡的，废校还是要废的。

军神的母亲西住志穗怒斥废校男，为了不造个大新闻，废校男承诺如果大洗学院可以打败大学队，就不用废校。

（有种 OI 选手 PK ACM 选手的感觉呀）

然而实力差距太大了，大洗女子学院最强的车是虎式 P 型，而大学队清一色的 M26 潘兴，M24 霞飞，还有能跑到 20 的 T95 和卡尔臼炮，感觉根本没法打呀。

这时候一个光头的胖子谢尔盖 • 布尔卡托夫斯基和一个身患癌症急需钱来治病的王姓 CEO 来帮助她们了。

他们把一堆真实性堪忧的坦克图纸给了大洗学院的妹子们，并说这些图纸是真的，而且还原了历史。

大洗学院汽车部的大家看到了这些图纸后非常高兴，开始膜改她们的战车。

虎式P型 -> 蟋蟀17

四号D型 -> 四号坦克武器运载车

38(t)型 -> 莱茵金属公司武器运载车

B1-bis  -> 105leFH18B2

即使这样，只有 8 辆战车的大洗女子学院仍然无法打败有 30 辆战车的大学队。

这时候按照剧本其他高中的小伙伴要来帮忙了，然而她们最近正在学习 OI，碰到了一道很神奇的数据结构题，不会做所以来不了。

你作为一个三次元的国家队选手，当然能秒杀二次元的 OI 题啦。

请帮帮她们吧！

description:
 ![](https://cdn.luogu.com.cn/upload/pic/4761.png)

给你一个 $n$ 个点的有根树， $1$ 为根，带边权，有 $m$ 次操作。

1、求 $x$ 的子树中第 $k$ 小的深度的值，如果子树中没有 $k$ 个点则输出 $-1$；

2、将 $x$ 与 $x$ 父亲的边权加上 $k$。

保证每次操作 2 的 $k$ 以及原树的边权小于等于一个数 $len$。

如果操作 2 中 $x$ 为 $1$，那么视为将 $x$ 的基础深度加上了 $k$。

inputFormat:
 ![](https://cdn.luogu.com.cn/upload/pic/4763.png)

第一行三个数 $n$、 $m$、$len$。

之后 $n - 1$ 行每行两个数表示 $2$~$n$ 每个点的父亲编号，以及他们到父亲的边权。

之后 $m$ 行每行三个数 $opt$、 $x$、$k$， $opt$ 表示操作种类， $x$、 $k$ 意义如题所述。

outputFormat: 对于每个操作 1，输出一个数表示答案。

hint:
数据范围与提示

对于 10% 的数据， $n, m \leq 1000$；

对于 30% 的数据， $n, m \leq 30000$；

对于 100% 的数据，$ n, m \leq 100000,len \leq 10$。

本水题采用捆绑测试，你只有通过该部分分的所有数据才可以得到该部分分的分数。

如果你对山口丁和 G&P 没有兴趣，可以无视结局。

如果你做出来了这个题

妹子们看了你的 STD 之后都 A 了这个题，然后去帮助军神。

她们找了 30 个 183 射了对面一脸。

如果你没做出来这个题

妹子们虽然很想帮助军神，但是也爱莫能助，毕竟学战车道不能保送。

没有办法，只能 8 打 30 了。

莱茵蹲在草里，大学队没有人发现它，成功击杀五辆敌方坦克后因为车体无法承受火炮后坐力而解体。

三突也蹲在草里，大学队没有人发现它，它也没有发现任何人，最后蹲不住了去突击，击毁一辆潘兴后被击毁。

四运文艺倒车，大学队看到之后目瞪口呆，成功击杀八辆敌方坦克后因为车体无法承受火炮后坐力而解体。

虎P炮一发带走了 95，然后因为转场的时候发动机故障而烧毁。

最后法五金刺刀了 15 个，成功翻盘。

![](https://cdn.luogu.com.cn/upload/pic/4762.png)


title: 夏幻的考试

background: 夏之幻是软件工程系的大神，学校把举办考试的任务交给她了。

description:
某大学软工专业要举办一场笔试，学生们要在机读答题卡上填写答案来进行答题。学校把机读卡识别任务交给了夏之幻，但是这套系统的需求太复杂了，她还要做自己的其他项(you)目(xi)，所以她想让你来帮忙实现一部分功能。

试卷分卷头，单选题两部分。

夏幻大神已经写好了识别程序，因此卷头和答案将直接以数字信息的形式呈现给你，你要实现下面几个功能:

需要处理T张试卷，按顺序检查下列选项。

1.检查考号的填写是否准确。

输入信息的格式:

一行，一个16位无符号二进制数id。表示考生的考号为id，正确的考号范围在十进制下是1~10000。

如果考号有错误，输出一行“Wrong ID”并结束对这张试卷的处理(剩下两个选项的数据依然要读入，但不输出任何内容)，不含引号。如果考号正确，输出一行,“ID: ”+一个整数，表示考号的十进制形式。不含引号。

无需考虑考号是否重复，只要在范围内均为正确。

2.检查试卷类型是否正确。

输入信息格式:

一行，两个整数，中间无分隔，只能是0或者1。第一个整数表示试卷类型A是否被涂黑(0表示未涂黑，1表示涂黑)，第二个整数表示试卷类型B是否涂黑。其实试卷类型可以由二进制考号的最后一位得到，0表示A卷，1表示B卷，你只需要检查考生填涂的是否正确。

如果考生将试卷类型正确填涂(填涂且只填涂了正确的那一项)，输出一行“Type Correct”，否则输出一行“Type Incorrect”，不含引号。无论试卷类型是否填涂正确，你还需要接着处理这张试卷。

3.给单选题打分。

单选题的数量n和标准答案将会在录入第一张试卷前给出。

考生答案的输入格式:

n行，每行4个整数，中间无分隔。每个整数是0或1。

按顺序分别代表A,B,C,D是否被涂黑(0表示未涂黑，1表示涂黑)。考生回答正确当且仅当该题正确答案的位置被涂黑，且错误答案的位置未被涂黑。

输出一行，一个四舍五入到小数点后1位的浮点数，表示考生的得分，满分为100分，每个题的分数相同。

inputFormat:
第一行两个整数T，n，空格分开，含义见题目描述。

接下来一行一个字符串s，长度为n，每个字符是大写字母A,B,C,D中的一个，第i个字符表示单选题i的答案。

接下来T\*(n+2)行含有T组信息，表示每张试卷的内容，格式见题目描述。

outputFormat: 对于每张试卷，输出评判结果，格式见题目描述。两张试卷的评判结果之间空一行。

samples:
Wrong ID

ID: 2
Type Correct
100.0

ID: 3
Type Incorrect
33.3

samples:
ID: 3009
Type Incorrect
87.1

ID: 1359
Type Incorrect
87.1

ID: 7270
Type Incorrect
87.1

ID: 5105
Type Incorrect
93.5

ID: 7300
Type Correct
87.1

hint:
对于100%的数据

1<=T<=1000

1<=n<=50

注意:

1.请在最后一个试卷处理完后也加上一个换行

2.由于win系统和linux系统换行的不同，建议不要使用scanf读入char