#P9596. [JOI Open 2018] 冒泡排序 2

[JOI Open 2018] 冒泡排序 2

题目描述

冒泡排序是一个对序列排序的算法。现在我们要将一个长度为 NN 的序列 A0,A1,,AN1A_0,A_1,\ldots ,A_{N-1}​ 按不降顺序排序。当两个相邻的数没有按正确顺序排列时,冒泡排序会交换这两个数的位置。每次扫描这个序列就进行这种交换。更确切地说,在一趟扫描中,对于 i=0,1,,N2i=0,1,\ldots ,N-2,并按这个顺序,如果 Ai>Ai+1A_i>A_{i+1}​,那么我们就交换这两个数的位置。众所周知任何序列经过有限趟扫描后一定可以按非降顺序排好序。对于一个序列 AA,我们定义用冒泡排序的扫描趟数为使用如上算法使得 AA 排好序的情况下所扫描的趟数。

JOI 君有一个长度为 NN 的序列 AA。他打算处理 QQ 次修改 AA 的值的询问。更明确地说,在第 (j+1) (0jQ1)(j+1)\ (0\le j\le Q-1) 次询问,AXjA_{X_j} 的值会变为 VjV_j

JOI 君想知道处理每次修改之后,用冒泡排序的扫描趟数。

输入格式

LOJ 上为交互题,方便起见,这里使用传统题的方式进行评测。

第一行两个整数 N,QN,Q

第二行 NN 个整数 A0,A1,,AN1A_0,A_1,\ldots ,A_{N-1}

接下来 QQ 行,每行两个整数 Xj,VjX_j,V_j

输出格式

输出 QQ 行,第 (j+1) (0jQ1)(j+1)\ (0\le j\le Q-1) 行表示处理第 (j+1)(j+1) 个询问后,对这个序列冒泡排序的扫描趟数。

4 2
1 2 3 4
0 3
2 1
1
2
11 12
11 4 13 6 7 3 5 12 4 10 11
8 11
4 4
6 20
0 2
7 2
3 18
5 9
0 6
8 8
9 4
0 8
6 18

5
5
5
4
6
6
6
7
7
7
7
7

提示

【样例解释】

给定一个长度为 N=4N=4 的序列 A={1,2,3,4}A=\{1,2,3,4\}Q=2Q=2 次询问:X={0,2},V={3,1}X=\{0,2\},V=\{3,1\}

  1. 对于第一次询问,A0A_0 的值变为 33。我们得到 A={3,2,3,4}A=\{3,2,3,4\}
  2. 对于第一次询问,A2A_2 的值变为 11。我们得到 A={3,2,1,4}A=\{3,2,1,4\}

A={3,2,3,4}A=\{3,2,3,4\} 做冒泡排序:

  • AA 并未排好序,所以第一趟扫描开始。因为 A0>A1A_0>A_1,所以我们交换它们,序列变为 A={2,3,3,4}A=\{2,3,3,4\}。因为 A1A2A_1\le A_2,所以我们不交换它们。因为 A2A3A_2\le A_3,所以我们也不交换它们。
  • 现在 AA 已经排好序了,所以冒泡排序过程结束。

因此对于 A={3,2,3,4}A=\{3,2,3,4\},冒泡排序的扫描趟数为 11

A={3,2,1,4}A=\{3,2,1,4\} 做冒泡排序:

  • AA 并未排好序,所以第一趟扫描开始。因为 A0>A1A_0>A_1,所以我们交换它们,序列变为 A={2,3,1,4}A=\{2,3,1,4\}。因为 A1>A2A_1> A_2,所以我们交换它们,序列变为 A={2,1,3,4}A=\{2,1,3,4\}。因为 A2A3A_2\le A_3,所以我们也不交换它们。
  • AA 并未排好序,所以第二趟扫描开始。因为 A0>A1A_0>A_1,所以我们交换它们,序列变为 A={1,2,3,4}A=\{1,2,3,4\}。因为 A1A2A_1\le A_2,所以我们不交换它们。因为 A2A3A_2\le A_3,所以我们也不交换它们。
  • 现在 AA 已经排好序了,所以冒泡排序过程结束。

因此对于 A={3,2,1,4}A=\{3,2,1,4\},冒泡排序的扫描趟数为 22

【数据范围】

共有四个子任务。每个子任务的分值及附加限制如下:

子任务编号 分值 NN QQ A,VA,V
11 1717 1N2 0001\le N\le 2\ 000 1Q2 0001\le Q\le 2\ 000 1Ai,Vj1091\le A_i,V_j\le 10^9
22 2121 1N8 0001\le N\le 8\ 000 1Q8 0001\le Q\le 8\ 000
33 2222 1N50 0001\le N\le 50\ 000 1Q50 0001\le Q\le 50\ 000 1Ai,Vj1001\le A_i,V_j\le 100
44 4040 1N500 0001\le N\le 500\ 000 1Q500 0001\le Q\le 500\ 000 1Ai,Vj1091\le A_i,V_j\le 10^9