P8650 - Fast Bubble Sort

内存限制：128 MB 时间限制：5 S

题面：传统评测方式：文本比较上传者：

提交：3 通过：1

Given an array

A = (a_{1}, a_{2}, \dots, a_{m})

of length

m

, denote by array

the output of a single iteration of bubble sort with input array

, i.e., the output of the following algorithm with input array

You may perform the following operation any number (including zero) of times on the array $A = (a_{1}, a_{2}, \dots, a_{m})$ :

Select an interval $[i, j]$ where $1 \leq i \leq j \leq m$ , and cyclically shift all elements of $a_{i}, a_{i + 1}, \dots, a_{j - 1}, a_{j}$ in either direction, so that they become $a_{j}, a_{i}, a_{i + 1}, \dots, a_{j - 1}$ or $a_{i + 1}, \dots, a_{j - 1}, a_{j}, a_{i}$ .

For example, if we cyclically shift the interval $]$ of the array to the right, the resulting array would be

You are now given a permutation $P = (p_{1}, p_{2}, \dots, p_{n})$ of length and you need to answer independent queries of the following form:

In the $i$ -th query, you are given parameters $1 \leq l_{i} \leq r_{i} \leq n$ and you are supposed to find the minimum number of above operations needed to transform the subarray $P [l_{i}, r_{i}]$ to $B (P [l_{i}, r_{i}])$ , where $P [l_{i}, r_{i}] = (p_{l_{i}}, p_{l_{i} + 1}, \dots, p_{r_{i}})$ .

The first line contains an integer $T (1 \leq T \leq 10)$ denote the number of test cases.

For each test case, the first line contains two integers $1 \leq n, q \leq 1 0^{5}$ ), denoting the length of permutation and the number of queries, respectively.

The second line contains distinct integers $p_{1}, p_{2}, \dots, p_{n}$ 1 $\leq p_{i} \leq n$ ).

Each of the following lines contains two integers $1 \leq l_{i} \leq r_{i} \leq n$ ), denoting the parameters for the -th query.

For each query of each test case, output an integer in one line, denoting the answer.

1
10 5
3 7 9 2 6 4 5 8 10 1
1 10
2 6
7 9
4 9
3 3

2022 杭电多校第九场

8650: Fast Bubble Sort

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签