#P15653. [Bulgarian2026训练营]PSORT

[Bulgarian2026训练营]PSORT

题目描述

Rosi 很喜欢数字,她把 11 到 nn 写在卡片上,打乱后排成一列,得到一个排列

P1,P2,…,Pn.P_1,P_2,\ldots,P_n.

Miro 看着她操作时,想出了下面这个游戏。

对于一个给定的数 KK,定义一次操作如下:按顺序枚举 i=1,2,…,K−1i=1,2,\ldots,K-1,如果当前 Pi>Pi+1P_i>P_{i+1},就交换 PiP_i 和 Pi+1P_{i+1}。

Miro 选择了一个非降序列

A=(A1,A2,…,Am),A=(A_1,A_2,\ldots,A_m),

其中 2≤Aj≤n2\le A_j\le n。他先对当前排列执行参数为 A1A_1 的操作,再对得到的新排列执行参数为 A2A_2 的操作,依此类推,直到执行完参数为 AmA_m 的操作。

每次操作后,他都想让 Rosi 告诉他当前排列的逆序对数量。

请写程序,求出每一步操作后的逆序对数量。

排列 PP 中的一个逆序对是一个有序下标对 (i,j)(i,j),满足 1≤i<j≤n1\le i<j\le n 且 Pi>PjP_i>P_j。

输入格式

第一行包含两个整数 n,mn,m。

第二行包含一个排列 P1,P2,…,PnP_1,P_2,\ldots,P_n。

第三行包含一个非降序列 A1,A2,…,AmA_1,A_2,\ldots,A_m。

输出格式

输出 mm 行。第 ii 行输出依次执行操作 A1,A2,…,AiA_1,A_2,\ldots,A_i 后,当前排列的逆序对数量。

数据范围

  • 2≤n≤2⋅1052\le n\le 2\cdot 10^5
  • 1≤m≤2⋅1051\le m\le 2\cdot 10^5
  • 2≤Ai≤n2\le A_i\le n
  • Ai≤Ai+1A_i\le A_{i+1},对所有 1≤i<m1\le i<m 成立。

子任务

子任务 分值 依赖子任务 限制 额外限制
0 - - 样例
1 8 n≤1000,m≤100n\le 1000, m\le 100 -
2 15 1 n≤104,m≤104n\le 10^4, m\le 10^4
3 13 - n≤2⋅105,m=1n\le 2\cdot 10^5, m=1
4 25 n≤2⋅105,m=n−1n\le 2\cdot 10^5, m=n-1 Ai=i+1A_i=i+1
5 39 1-4 n≤2⋅105,m≤2⋅105n\le 2\cdot 10^5, m\le 2\cdot 10^5 -

只有通过某个子任务及其所有依赖子任务中的全部测试,才能获得该子任务分数。

样例

3 2
3 1 2
2 3
1
0

样例说明

执行 A1=2A_1=2 的操作后,排列变为 (1,3,2)(1,3,2),逆序对数量为 11。

执行 A2=3A_2=3 的操作后,排列变为 (1,2,3)(1,2,3),逆序对数量为 00。