Theme NexT works best with JavaScript enabled

## A - Graph Games

### 题目描述

You are given an undirected graph with $N$ vertices and $M$ edges. The edges are numbered from $1$ to $M$ . Denote the set $S(x)$ as: All the vertices we can reach from vertex $x$ by exactly one edge.

You are supposed to deal with $Q$ operations of the following two types:

• $(1,l,r)$ — reverse the status of edges numbered between $l$ to $r$ $(1 \leq l \leq r \leq M)$ . i.e. Delete the edge if it is in the graph, otherwise add it to the graph.
• $(2,u,v)$ — ask whether $S(u)$ and $S(v)$ are exactly the same $(1 \leq u \leq v \leq N)$ .

Note that all the $M$ edges are in the graph at the beginning.

### 输入描述

The input contains multiple cases. The first line of the input contains a single positive integer $T$ , the number of cases.

For each case, the first line contains two integers $N\ (1 \leq N \leq 100000)$ and $M\ (1 \leq M \leq 200000)$ , the number of vertices and edges in the graph. In the following $M$ lines, the $i$ -th line contains two integers $u_i,v_i \ (1 \le u_i,v_i \le N)$ , describing the the $i$ -th edge $(u_i,v_i)$ . Each edge appears in the input at most once. The $(M+2)$ -th line contains a integer $Q\ (1 \leq Q \leq 200000)$ , the number of operations. In the following $Q$ lines, each line contains three integers, describing an operation.

The total sum of $N$ over all cases does not exceed $150000$ .

The total sum of $M$ over all cases does not exceed $800000$ .

The total sum of $Q$ over all cases does not exceed $600000$ .

### 输出描述

For each case, print a string in a line. The length of the string should equal the number of operations of type $2$ . If the answer is yes, the $i$ -th character of the string should be 1, otherwise it should be 0. Check the samples for more details.

### 题解

#### 题意

• 1 l r 将读入的边的序列的区间 $[l,r]$ 内的边反转状态（有/无），初始为全有
• 2 x y 询问 $x$ 和 $y$ 两个点所直连的点构成的两个点集是否相同

#### 解法

• 对于轻点，边数不超过 $\sqrt{m}$ ，直接暴力判断是否翻转。
• 对于重点，只有 $\sqrt{m}$ 种。对边序列分块，维护每一个块如果整体翻转对某个重点集的贡献。在进行区间操作的时候，在块间打翻转标记，在两侧暴力翻转。如果翻转的边的端点是重点，就直接计算一次贡献。询问时查询所有块的整体翻转情况，如果整体是翻转的，则再计算一次贡献。这样每次询问复杂度 $\mathcal{O}(\sqrt{m})$ 。

## B - Crazy Binary String

### 题目描述

ZYB loves binary strings (strings that only contains 0 and 1). And he loves equal binary strings\textit{equal binary strings}equal binary strings more, where the number of 0 and the number of 1 in the string are equal.

ZYB wants to choose a substring from an original string $T$ so that it is an $\text{equal binary string}$ with the longest length possible. He also wants to choose a subsequence of $T$ which meets the same requirements.

A string $v$ is a substring of a string $w$ if $v$ is empty, or there are two integers $l$ and $r \ (1 \le l \le r \le |w|)$ such that $v=w_lw_{l+1}\cdots w_r$ . A string $v$ is a subsequence of a string $w$ if it can be derived from $w$ by deleting any number (including zero) of characters without changing the order of the remaining characters.

For simplicity, you only need to output the maximum possible length. Note that the empty string is both a substring and a subsequence of any string.

### 输入描述

The first line of the input contains a single integer $N \ (1 \le N \leq 100000)$ , the length of the original string $T$ . The second line contains a binary string with exactly $N$ characters, the original string $T$ .

### 输出描述

Print two integers $A$ and $B$ , denoting the answer for substring and subsequence respectively.

### 题解

#### 解法

• 子串

• 令 $f_{i}$ 表示前 $i$ 个字符中01的数量差，那么答案为相距最远且值相同的一对 $f_i$ 与 $f_j$ 的距离，即 $\max(i-j|f_i=f_j)$
• 对于每一个差值，记录它在 $f$ 数组中第一次出现的下标，每次遇到出现过的 $f_i$ ,把它与答案比对即可。
• 子序列

• 子序列可以任取，因此01里面数量最少的那个对答案有限制。令字符串中01的数量分别为 $n_{0}$ 和 $n_{1}$ ，答案为 $2 \times \min(n_0,n_1)$

## C - Guessing ETT

### 题目描述

ZYB is a smart guy.

One day he learns a new method for representing trees: Euler tour technique (ETT).

You can find more details about ETT on this web page:

https://blog.nowcoder.net/n/7afe88dc36ef4649b4de941f08abf576

If we use vertices rather than edges in ETT, then any tree with $N$ vertices corresponds to a sequence of length $2N-1$ , let’s call it the vertex-ETT sequence.

In the beginning, ZYB generates a tree (the root of that tree is always 1) and writes down its vertex-ETT sequence.

However, he spilt ink onto the paper by mistake and some numbers were covered in ink.

Can you help him to restore the sequence?

### 输入描述

There are multiple test cases. The first line of the input contains an integer $T$ , indicating the number of test cases.

For each test case, the first line contains a integer $N$ ( $1 \leq N \leq 2.5 \times 10^5$ ) , while the second line contains an integer sequence $a$ ( $1 \leq a_i \leq N$ or $a_i=-1$ ) , which means this number was covered by the ink) of length $2N-1$ , the vertex-ETT sequence.

it is guaranteed that at least one valid sequence exists.

It’s guaranteed that the sum of $N$ of all test cases will not exceed $500000$ .

Due to the large size of the input, it’s recommended to use a fast way to read the input.

### 输出描述

For each case, print $2N-1$ space-separated integers, the recovered sequence.
If there are multiple solutions, print any of them.

## D - Big Integer

### 题目描述

For little pupils, a very large number usually means an integer with many many digits. Let’s define a class of big integers which consists only of the digit one $(11 \cdots 1)$ . The first few integers in this class are $1, 11, 111, 1111 \cdots$ . Denote $A(n)$ as the $n$ -th smallest integer in this class. To make it even larger, we consider integers in the form of $A(a^b)$ . Now, given a prime number $p$ , how many pairs $(i, j)$ are there such that $1 \leq i \leq n,\ 1 \leq j \leq m,\ A(i^j) \equiv 0(mod \ p)$ .

### 输入描述

The input contains multiple cases. The first line of the input contains a single integer $T \ (1 \le T \le 100)$ , the number of cases.
For each case, the input consists of a single line, which contains $3$ positive integers $p, n, m \ (p, n, m \leq 10^9)$ .

### 输出描述

Print the answer, a single integer, in one separate line for each case.

### 题解

#### 解法

$11⋯111=10n−19≡0(\mod p)$ 等价于 $10n≡1(\mod 9p)$

$ϕ(9p)$ 是欧拉函数，这个式子由欧拉定理可知

”显然成立“部分证明：

## E - Trees in the Pocket II

### 题目描述

DreamGrid has just found two trees, both consisting of n vertices, in his right pocket. Each edge in each tree has its own weight. The i-th edge in the first tree has a weight of $a_{i}$ , while the i-th edge in the second tree has a pair of weight, denoted by $(b_i, c_i)$ .

Let ${}^1u$ be the $u$ -th vertex in the first tree, and ${}^2u$ be the $u$ -th vertex in the second tree. Let $\mathbb{E}_1({}^1u, {}^1v)$ be the set containing the indices of all the edges on the path between the $u$ -th and the $v$ -th vertex in the first tree. Similarly, let $\mathbb{E}_2({}^2u, {}^2v)$ be the set containing the indices of all the edges on the path between the $u$ -th and the $v$ -th vertex in the second tree. Define the following values:

$A_{\min}({}^1u, {}^1v) = \min\{a_k | k \in \mathbb{E}_1({}^1u, {}^1v)\}$

$B_{\max}({}^2u, {}^2v) = \max\{b_k | k \in \mathbb{E}_2({}^2u, {}^2v)\}$

$C_{\max}({}^2u, {}^2v) = \max\{c_k | k \in \mathbb{E}_2({}^2u, {}^2v)\}$

As DreamGrid is bored, he decides to count the number of good indices. DreamGrid considers an index $i (1 \le i \le n)$ is good, if for all $1 \le j \le n$ and $j \ne i$ , $A_{\min}({}^1i, {}^1j) \ge \min(B_{\max}({}^2i, {}^2j), C_{\max}({}^2i, {}^2j))$ . Please help DreamGrid figure out all the valid indices.

You may have seen this problem before, but this time we need you to have an $O(N \log N)$ solution, or it may not pass.

### 输入描述

There are multiple test cases. The first line contains an integer $T$ , indicating the number of test cases. For each test case:

The first line contains an integer $n (2 \le n \le 10^5)$ indicating the number of vertices in both trees.

For the following $(n-1)$ lines, the $i$ -th line contains three integers ${}^1u_i$ , ${}^1v_i$ and $a_i (1 \le {}^1u_i, {}^1v_i$ , $1 \le a_i \le 10^9)$ , indicating that there is an edge, whose weight is $a_i$ , connecting vertex $u_i$ and $v_i$ in the first tree.

For the following $(n-1)$ lines,the $i$ -th line contains four integers ${}^2u_i$ , ${}^2v_i$ , $b_i$ and $c_i$ ( $1 \le {}^2u_i, {}^2v_i \le n$ , $1 \le b^2_i, c^2_i \le 10^9$ ), indicating that there is an edge, whose weight is $(b_i, c_i)$ , connecting vertex $u_i$ and $v_i$ in the second tree.

It’s guaranteed that the sum of $n$ of all test cases does not exceed $2 \times 10^5$ .

### 输出描述

For each test case output $k$ integers ( $k$ is the number of valid indices) in one line separated by a space in increasing order, indicating the indices of the valid vertices.

Note that if there is no valid vertex, you should print -1 instead.

## F - Planting Trees

### 题目描述

The semester is finally over and the summer holiday is coming. However, as part of your university’s graduation requirement, you have to take part in some social service during the holiday. Eventually, you decided to join a volunteer group which will plant trees in a mountain.

To simplify the problem, let’s represent the mountain where trees are to be planted with an $N \times N$ grid. Let’s number the rows $1$ to $N$ from top to bottom, and number the columns $1$ to $N$ from left to right. The elevation of the cell in the $i$ -th row and $j$ -th column is denoted by $a_{i,j}$ . Your leader decides that trees should be planted in a rectangular area within the mountain and that the maximum difference in elevation among the cells in that rectangle should not exceed M. In other words, if the coordinates of the top-left and the bottom-right corners of the rectangle are $(x_1,y_1)$ and $(x_2,y_2)$ , then the condition $|a_{i,j} - a_{k,l}| \le M$ must hold for $x_1 \le i,k \le x_2, \ y_1 \le j,l \le y_2$ . Please help your leader calculate the maximum possible number of cells in such a rectangle so that he’ll know how many trees will be planted.

### 输入描述

The input contains multiple cases. The first line of the input contains a single integer $T \ (1 \le T \le 1000)$ , the number of cases.

For each case, the first line of the input contains two integers $N\ (1 \le N \le 500)$ and $M\ (0 \le M \le 10^5)$ . The following $N$ lines each contain $N$ integers, where the $j$ -th integer in the $i$ -th line denotes $a_{i,j} \ (1 \le a_{i,j} \le 10^5)$ .

It is guaranteed that the sum of $N^3$ over all cases does not exceed $25 \cdot 10^7$ .

### 输出描述

For each case, print a single integer, the maximum number of cells in a valid rectangle.

## G - Removing Stones

### 题目描述

Summer vacation is coming and Mark has returned home from his university having successfully survived the exam week. Today, he is very bored. So his friend Alice challenges him to play a game with stones which is invented by her. Alice gives Mark $N$ piles of stones numbered from $1$ to $N$ , and there are $a_i$ stones in the $i$ -th pile. The rules of the game are simple: Mark will try to remove all stones. In each move, Mark chooses two different non-empty piles and removes one stone from each of those two piles. Mark can perform any number of moves. If all the piles are empty after some number of moves, Mark wins the game. If he can’t make a valid move but not all piles are empty, he loses the game. Obviously, if the total number of stones is odd, then Mark is not able to win the game. So there is an additional rule: if initially, the total number of stones is odd, then Mark removes a single stone from the pile with the fewest stones before starting the game. If there are multiple piles with the smallest number of stones, Mark chooses one among them to remove a stone.

Mark found the optimal strategy for Alice’s game very quickly and gets bored again. Also, he noticed that for some configuration of stones there is no way to win. So he challenges you to solve this problem: count the number of integer pairs $(l,r) \ (1 \le l < r \le N)$ such that it is possible for Mark to win the game if the game is played using only the piles numbered from $l$ to $r$ .

### 输入描述

The input contains multiple cases. The first line of the input contains a single positive integer $T$ , the number of cases.

The first line of each case contains a single integer $N \ (2 \le N \le 300000)$ , the number of piles. The following line contains $N$ space-separated integers, where the $i$ -th integer denotes $a_i \ (1 \le a_i \le 10^9)$ , the number of stones in the $i$ -th pile.

It is guaranteed that the sum of $N$ over all cases does not exceed $1000000$ .

### 输出描述

For each case, print a single integer on a single line, the number of pairs satisfying the required property.

## H - Magic Line

### 题目描述

There are always some problems that seem simple but is difficult to solve.

ZYB got $N$ distinct points on a two-dimensional plane. He wants to draw a magic line so that the points will be divided into two parts, and the number of points in each part is the same. There is also a restriction: this line can not pass through any of the points.

Help him draw this magic line.

### 输入描述

There are multiple cases. The first line of the input contains a single integer $T \ (1 \leq T \leq 10000)$ , indicating the number of cases.

For each case, the first line of the input contains a single even integer $N \ (2 \leq N \leq 1000)$ , the number of points. The following $N$ lines each contains two integers $x_i, y_i \ (|x_i, y_i| \leq 1000)$ , denoting the x-coordinate and the y-coordinate of the $i$ -th point.

It is guaranteed that the sum of $N$ over all cases does not exceed $2 \times 10^5$ .

### 输出描述

For each case, print four integers $x_1, y_1, x_2, y_2$ in a line, representing a line passing through $(x_1, y_1)$ and $(x_2, y_2)$ . Obviously the output must satisfy $(x_1,y_1) \ne (x_2,y_2)$ .

The absolute value of each coordinate must not exceed $10^9$ . It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.

## I - Median

### 题目描述

JSB has an integer sequence $a_1, a_2, \dots, a_n$ . He wants to play a game with SHB.

For each $1 \le i \le n-2$ , JSB calculates the median of $\{a_i, a_{i+1}, a_{i+2}\}$ , denoted by $b_i$ . SHB is given the sequence $b_1, b_2, \dots, b_{n-2}$ . Can you help him restore the sequence $a$ ?

Recall that the median of three numbers is the second largest one of them.

### 输入描述

There are multiple cases. The first line of the input contains a single positive integer $T$ , indicating the number of cases.

For each case, the first line of the input contains a single integer $n\ (3 \le n \le 10^5)$ , the length of the sequence $a$ . The second line contains $n-2$ integers $b_1, b_2, \dots, b_{n-2}\ (0 \le b_i \le 10^9)$ .

It’s guaranteed that the sum of $n$ over all cases does not exceed $10^6$ .

### 输出描述

For each case print one line containing $n$ integers, indicating the sequence $a_1, a_2, \dots, a_n$ . Your output must satisfy $0 \le a_i \le 10^9$ for each $1 \le i \le n$ .

If there are multiple valid answers, you may print any of them. If there is no valid answer, print”-1” (without quotes) instead.

## J - LRU management

### 题目描述

ZYB has finished his computer course recently. He is very interested in the LRU algorithm for cache management.

To simplify the problem, assume that a block contains a name (which is a string) and a set of data (which is a number). ZYB wants to implement the LRU algorithm with an array.

His array can hold at most $M$ elements at any time. In the beginning, the array is empty. In each operation, the CPU may access a block $s$ . ZYB will search for it in his array by brute force. If this block is present in his array (which means he can find a block with the same name), he takes it out of the array and puts it back at the end of the array. Otherwise, he simply adds it to the end of the array. If at any time, the size of the array exceeds the capacity, he will remove the first block in his array (the block at the front of the array).

Seems boring? Well, sometimes ZYB may ask the data of a block in, before or after a certain block. Could you help him to write a program to achieve his goal?

### 输入描述

There are multiple cases. The first line of the input contains a single positive integer $T$ , indicating the number of cases.

For each case, the first line of the input contains two integers $Q$ and $M\ (1 \leq Q, \ M \leq 500000)$ , denoting the number of operations and the capacity of the array. The following $Q$ lines each contain an integer $opt \ (0 \le opt \le 1)$ , a string $s \ (1 \leq |s| \leq 10)$ and an integer $v$ , separated by single spaces, describing an operation.

If $opt = 0$ , then $|v| < 10$ , and the operation is that the CPU wants to access a block. If this access misses (which means you can’t find a block in the array with the name $S$ ), add a block at the end of the array with the name $S$ and the data $V$ , and the result of the operation is $V$ . If this access hits, the result of the operation is the data of the block you found (ignore $V$ in this case). Don’t forget to move that block to the end of the array.

If $opt = 1$ , then $v$ will be $-1,0$ or $1$ , and the operation is that you should answer ZYB’s question. Let $k$ be the index of the block with the name $s$ in the array. Then the result of this operation is the data of the block with the index $k+v$ in the array. If such block doesn’t exist, please output “Invalid’’ (without quotation marks) instead.

Note that ZYB’s questions (operations of type $1$ ) don’t count as access and don’t cause the array to be updated.

It is guaranteed that the sum of $Q$ over all cases does not exceed $1000000$ , and that $s$ only contains digits (i.e. 0 - 9).

### 输出描述

For each case, print the result of each operation in a line as defined in the input section of the statement.