| Problem description | | Progress |
|
Темы:
Binary search tree
Farmer John's Cow Organization (UCFJ) sends a delegation to the International Sheep Olympiad (IOI).
N cows participate in the delegation selection (1≤N≤2⋅105). They stand in a row, and cow i has breed bi.
The delegation consists of a contiguous range of at least two cows - i.e. l…r cows for integers l and r satisfying 1≤l<r≤N. the two outer cows of the selected interval are called "leaders". To avoid conflict between breeds of cows, each leader must have a breed different from the other cows of the delegation (leaders and non-leaders).
Specify the number of ways to select a delegation.
Input:
The first line contains N.
The second line contains N integers b1,b2,…,bN, each in the interval [1,N].
Output:
The number of possible delegations, on a separate line.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
7
1 2 3 4 3 2 5
| 13 |
Each delegation corresponds to one of the following leader pairs:
(1.2),(1.3),(1.4),(1.7),(2.3),(2.4),(3.4),(4.5),(4 ,6),(4,7),(5,6),(5,7),(6,7). |
| |
![]()
|
|
Темы:
Binary search tree
Simulation tasks
Physicists are conducting an experiment to study particles of three types: x, y and z. They launch a numbered row of n particles into the collider. During the experiment, one specific particle is affected, after which the particle disappears from the i-th place of the row and instantly appears at the place j. After it disappears, the numbers of particles to the right decrease by 1, and after the appearance, the numbers of particles to the right increase by 1. After a certain number of impacts, physicists are interested in which particle is in place k. Write a program to help physicists.
Input
The first line of the file contains two integers: n – number of particles and m — total number of exposures and questions (1 ≤ n ≤ 1000000, 1 ≤ m ≤ 15000). On the second line — a sequence of characters x, y and z of length n. Each of the next m lines (1 ≤ m ≤ 15000) describes an impact or question. The line, which describes the impact, begins with the character a and after the space two integers from the interval [1; n]. The first of them shows the initial, and the second - the final location of the particle during the impact. The line in which the question is described begins with the symbol q and after a space one integer from the interval [1; n]. It indicates the position that physicists are interested in.
Imprint
Output as many lines as there are questions in the input file. In line number i you need to write the answer to the question i — the name of the corresponding particle x, y or z.
Explanations for example
The sequence after the first exposure – xxyyzxxzxzyyzyx, the sequence after the second exposure – xxyxyzxxzxzyyzy, sequence after the third exposure –
Examples
| # |
Input |
Output |
| 1 |
15 6
xzxyyzxxzxyyzyx
a 2 10
a 15 4
q 3
a 12 2
q 14
q2 |
y
z
y |
| |
![]()
|