← 返回比赛

已结束 MMOI Round 1

← 上一题下一题 →

A7397 | $刷怪塔$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

在修建好刷怪塔后，Steve 需要运输怪物掉落的物品。具体地，有 $n$ 层刷怪平台，其中第 $i$ 层掉落的物品需要运往第 $p_i$ 层。保证 $p$ 是一个 $1\sim n$ 的排列。 Steve 发现将物品向上运输是困难的，于是他想要将最高的 $x$ 层刷怪平台改为接收平台，此时第 $i$ 层的物品能被运往第 $p_i$ 层，即满足目标的条件为： * 第 $i$ 层平台没有被改为接收平台，即 $i\le n-x$； * 第 $p_i$ 层平台的高度小于等于第 $i$ 层平台的高度，即 $p_i\le i$；或者第 $p_i$ 层平台被改为接收平台，即 $p_i>n-x$。 Steve 想让你帮他将 $x$ 的值设置为 $0$ 到 $n$ 之间的某个数，使得满足目标的平台层数尽量多。 同时你还需要支持 $q$ 次修改，每次修改给出 $x,y$，表示交换 $p_x,p_y$ 的值，你需要在所有修改前和每次修改后输出目前最多能有多少个平台满足目标。

输入格式

输入的第一行包含一个整数 $c$，表示测试点编号。 第二行包含两个正整数 $n,q$，分别表示刷怪平台的数量和修改的次数。 第三行包含 $n$ 个正整数 $p_1,p_2,\dots,p_n$，其中 $p_i$ 表示第 $i$ 层平台中掉落的物品的目标平台。 接下来 $q$ 行，每行两个正整数 $x,y$，表示交换 $p_x$ 和 $p_y$ 的值。

输出格式

输出 $q+1$ 行，每行一个整数，其中第 $i$ 行的整数表示进行前 $i-1$ 次操作后的答案。

输入输出样例

输入 #1

0
8 5
4 1 7 2 8 3 6 5
1 5
3 7
2 8
4 6
1 7

输出 #1

【样例解释】 对于修改之前的序列，一种最优的方案是取 $x=0$，此时满足目标的平台 $i$ 有 $2,4,6,7,8$。 【数据范围】 测试点编号特殊性质$1-2$$n,q\le 100$$3-4$$n,q\le 10^3$$5-6$$p_i=n-i+1,q=0$$7-10$无 对于 $100\%$ 的测试点，保证：$1\le n\le 2\times 10^5$，$0\le q\le 2\times10^5$，$1\le x,y\le n$。

C++ 编辑器

输入

输出