时空限制

3.5S/1024M

题目描述

给定一个长度为 $n$ 的排列 $P = (p_1, p_2, \dots, p_n)$。

现在有 $q$ 次独立的询问。每次询问会给出两个不相交的区间 $[l_1, r_1]$ 和 $[l_2, r_2]$。

对于每次询问，你需要回答：如果将排列 $P$ 中位于区间 $[l_1, r_1]$ 的子段和位于区间 $[l_2, r_2]$ 的子段进行交换，新得到的排列的逆序对数量是多少？

每次询问都是独立的，即一次询问中的交换操作不会影响下一次询问，所有操作都基于初始排列 $P$。

• 一个长度为 $n$ 的排列是指由 $1, 2, \dots, n$ 这 $n$ 个整数组成的一个序列，其中每个整数恰好出现一次。

• 一个排列的逆序对是指满足 $i < j$ 且 $p_i > p_j$ 的数对 $(i, j)$ 的数量。

格式

输入格式

第一行包含两个整数 $n, q$，分别表示排列的长度和询问的数量。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示初始排列。

接下来的 $q$ 行，每行包含四个整数 $l_1, r_1, l_2, r_2$，描述一次询问的两个区间。保证 $r_1 < l_2$。

输出格式

对于每次询问，输出一行，包含一个整数，表示交换区间后新排列的逆序对数量。

样例

样例输入 #1

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

样例输出 #1

4
9

样例解释 #1

第一个询问：将这两个子段交换，排列变为：$[1, \underline{2, 4}, 6, \underline{5, 3}]$。

第二个询问：将这两个子段交换，排列变为：$[\underline{4} ,3 ,6 ,2, \underline{1 ,5}]$。

数据规模

对于 $30\%$ 的数据， $2 \leq n , q \leq 1000$。

对于 $100\%$ 的数据，$2 \leq n ,q \leq 10^5$， $1 \leq l_1 \leq r_1 < l_2 \leq r_2 \leq n$，$p$ 是一个排列。