The Ultimate LIS Problem

题意翻译

给定一个长为 $2n+1$ 的排列，然后进行 $m$ 次操作，每次操作是交换 $p_{u_i}$ 与 $p_{v_i}$。 在每次操作后，找到一个 $k$，使得排列向左循环移位 $k$ 次后得到的排列的 LIS 小于等于 $n$，或判断不存在这样的 $k$。 向左循环移位 $k$ 次后的排列是 $\{p_{k+1},...,p_n,p_1,...,p_k\}$。 第一行 $n,m$。$(n,m\le10^5)$ 第二行 $2n+1$ 个数表示这个排列。 接下来 $m$ 行每行一个操作。

题目描述

It turns out that this is exactly the $ 100 $ -th problem of mine that appears in some programming competition. So it has to be special! And what can be more special than another problem about LIS... You are given a permutation $ p_1, p_2, \ldots, p_{2n+1} $ of integers from $ 1 $ to $ 2n+1 $ . You will have to process $ q $ updates, where the $ i $ -th update consists in swapping $ p_{u_i}, p_{v_i} $ . After each update, find any cyclic shift of $ p $ with $ LIS \le n $ , or determine that there is no such shift. (Refer to the output section for details). Here $ LIS(a) $ denotes the length of [longest strictly increasing subsequence](https://en.wikipedia.org/wiki/Longest_increasing_subsequence) of $ a $ . Hacks are disabled in this problem. Don't ask why.

输入输出格式

输入格式

The first line of the input contains two integers $ n, q $ ( $ 2 \le n \le 10^5 $ , $ 1 \le q \le 10^5 $ ). The second line of the input contains $ 2n+1 $ integers $ p_1, p_2, \ldots, p_{2n+1} $ ( $ 1 \le p_i \le 2n+1 $ , all $ p_i $ are distinct) — the elements of $ p $ . The $ i $ -th of the next $ q $ lines contains two integers $ u_i, v_i $ ( $ 1 \le u_i, v_i \le 2n+1 $ , $ u_i \neq v_i $ ) — indicating that you have to swap elements $ p_{u_i}, p_{v_i} $ in the $ i $ -th update.

输出格式

After each update, output any $ k $ $ (0 \le k \le 2n) $ , such that the length of the longest increasing subsequence of $ (p_{k+1}, p_{k+2}, \ldots, p_{2n+1}, p_1, \ldots, p_k) $ doesn't exceed $ n $ , or $ -1 $ , if there is no such $ k $ .

输入输出样例

输入样例 #1

2 6
1 2 3 4 5
1 5
1 5
4 5
5 4
1 4
2 5

输出样例 #1

-1
-1
2
-1
4
0

说明

After the first update, our permutation becomes $ (5, 2, 3, 4, 1) $ . We can show that all its cyclic shifts have $ LIS \ge 3 $ . After the second update, our permutation becomes $ (1, 2, 3, 4, 5) $ . We can show that all its cyclic shifts have $ LIS \ge 3 $ . After the third update, our permutation becomes $ (1, 2, 3, 5, 4) $ . Its shift by $ 2 $ is $ (3, 5, 4, 1, 2) $ , and its $ LIS = 2 $ . After the fourth update, our permutation becomes $ (1, 2, 3, 4, 5) $ . We can show that all its cyclic shifts have $ LIS \ge 3 $ . After the fifth update, our permutation becomes $ (4, 2, 3, 1, 5) $ . Its shift by $ 4 $ is $ (5, 4, 2, 3, 1) $ , and its $ LIS = 2 $ . After the fifth update, our permutation becomes $ (4, 5, 3, 1, 2) $ . Its shift by $ 0 $ is $ (4, 5, 3, 1, 2) $ , and its $ LIS = 2 $ .

**最长递增子序列的终极问题**

**题意翻译**
给定一个长度为 $2n+1$ 的排列，然后进行 $m$ 次操作，每次操作是交换 $p_{u_i}$ 与 $p_{v_i}$。

在每次操作后，找到一个 $k$，使得排列向左循环移位 $k$ 次后得到的排列的 LIS 小于等于 $n$，或判断不存在这样的 $k$。

向左循环移位 $k$ 次后的排列是 $\{p_{k+1},...,p_{2n+1},p_1,...,p_k\}$。

第一行输入 $n,m$。$(n,m\le10^5)$

第二行输入 $2n+1$ 个数表示这个排列。

接下来 $m$ 行每行一个操作。

**题目描述**
这已经是我出现在某程序设计竞赛中的第 $100$ 个问题。所以它必须是特别的！还有什么比另一个关于 LIS 的问题更特别...

给定一个排列 $ p_1, p_2, \ldots, p_{2n+1} $，由 $ 1 $ 到 $ 2n+1 $ 的整数组成。你将处理 $ q $ 个更新，其中第 $ i $ 个更新包括交换 $ p_{u_i}, p_{v_i} $。

在每次更新后，找到任何具有 $ LIS \le n $ 的 $ p $ 的循环移位，或者确定不存在这样的移位。（详情请参见输出部分）。

这里 $ LIS(a) $ 表示序列 $ a $ 的[最长严格递增子序列](https://en.wikipedia.org/wiki/Longest_increasing_subsequence)的长度。

此问题**最长递增子序列的终极问题** **题意翻译** 给定一个长度为 $2n+1$ 的排列，然后进行 $m$ 次操作，每次操作是交换 $p_{u_i}$ 与 $p_{v_i}$。 在每次操作后，找到一个 $k$，使得排列向左循环移位 $k$ 次后得到的排列的 LIS 小于等于 $n$，或判断不存在这样的 $k$。 向左循环移位 $k$ 次后的排列是 $\{p_{k+1},...,p_{2n+1},p_1,...,p_k\}$。 第一行输入 $n,m$。$(n,m\le10^5)$ 第二行输入 $2n+1$ 个数表示这个排列。 接下来 $m$ 行每行一个操作。 **题目描述** 这已经是我出现在某程序设计竞赛中的第 $100$ 个问题。所以它必须是特别的！还有什么比另一个关于 LIS 的问题更特别... 给定一个排列 $ p_1, p_2, \ldots, p_{2n+1} $，由 $ 1 $ 到 $ 2n+1 $ 的整数组成。你将处理 $ q $ 个更新，其中第 $ i $ 个更新包括交换 $ p_{u_i}, p_{v_i} $。 在每次更新后，找到任何具有 $ LIS \le n $ 的 $ p $ 的循环移位，或者确定不存在这样的移位。（详情请参见输出部分）。 这里 $ LIS(a) $ 表示序列 $ a $ 的[最长严格递增子序列](https://en.wikipedia.org/wiki/Longest_increasing_subsequence)的长度。 此问题