#CSPS2020D. 贪吃蛇(Greedy Snake)

贪吃蛇(Greedy Snake)

题目描述

草原上有 nn 条蛇,编号分别为 1,2,,n1,2,\cdots,n。初始时每条蛇有一个体力值 aia_i,我们称编号为 xx 的蛇实力比编号为 yy 的蛇强当且仅当它们当前的体力值满足 ax>aya_x>a_y,或者 ax=aya_x=a_yx>yx>y

接下来这些蛇将进行决斗,决斗将持续若干轮,每一轮实力最强的蛇拥有选择权,可以选择吃或者不吃掉实力最弱的蛇:

  1. 如果选择吃,那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值,实力最弱的蛇被吃掉,退出接下来的决斗。之后开始下一轮决斗。

  2. 如果选择不吃,决斗立刻结束。

每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇(显然,蛇不会选择吃自己)。

现在假设每条蛇都足够聪明,请你求出决斗结束后会剩几条蛇。

本题有多组数据,对于第一组数据,每条蛇体力会全部由输入给出,之后的每一组数据,会相对于上一组的数据,修改一部分蛇的体力作为新的输入。

输入格式

输入文件名为 snakes.in

第一行一个正整数 TT,表示数据组数。

接下来有 TT 组数据,对于第 11 组数据,第一行一个正整数 nn,第二行 nn 个非负整数表示 aia_i
对于第 22 组到第 TT 组数据,每组数据:
第一行第一个非负整数 kk 表示体力修改的蛇的个数。
第二行 2k2k 个整数,每两个整数组成一个二元组 (x,y)(x,y),表示依次将 axa_x 的值改为 yy。一个位置可能被修改多次,以最后一次修改为准。

输出格式

输入文件名为 snakes.out

输出 TT 行,每行一个整数表示最终存活的蛇的条数。

2
3
11 14 14
3
1 5 2 6 3 25
3
1
2
5
13 31 33 39 42
5
1 7 2 10 3 24 4 48 5 50
5
3

样例 3

见附加文件中的 snakes3.insnakes3.ans

样例 4

见附加文件中的 snakes4.insnakes4.ans

数据范围与提示

对于 20%20\% 的数据:n=3n=3
对于 40%40\% 的数据:n10n\le 10
对于 55%55\% 的数据:n2×103n\le 2\times 10^3
对于 70%70\% 的数据:n5×104n\le 5\times 10^4
对于 100%100\% 的数据:3n1063\le n\le 10^61T101\le T\le 100k1050\le k\le 10^50ai,y1090\le a_i,y\le 10^9。保证每组数据(包括所有修改完成后的)的 aia_i 以不降顺序排列。