[AMPPZ2014]The Staging

时间限制:50s      空间限制:256MB

题目描述

在舞台上有n个枪手,第i个枪手瞄准了第p[i]个枪手,将于第u[i]秒开枪。一个枪手如果成功开枪,
那么被瞄准的枪手会立刻死亡。
现在给出q次修改操作,请在一开始和每次修改操作后统计出最后存活的枪手个数。


输入格式

第一行包含一个正整数n(1<=n<=200000),表示枪手的个数。
第二行包含n个互不相同的正整数p[1],p[2],...,p[n](1<=p[i]<=n,p[i]!=i),依次表示每个枪手的目标。
第三行包含n个正整数u[1],u[2],...,u[n](1<=u[i]<=10^9),依次表示每个枪手的开枪时间。
接下来一行包含一个正整数q,表示修改操作的个数。
接下来q行,每行包含两个正整数k,v(1<=k<=n,1<=v<=10^9),表示把u[k]修改为v。
数据保证任何时刻任意两个枪手的开枪时间都不同。


输出格式

第一行包含一个正整数,即在进行修改之前最后存活的枪手个数。
接下来q行,每行包含一个正整数,第i行输出在第i次修改之后最后存活的枪手个数。


样例输入

4
2 3 4 1
1 2 3 4
3
1 8
2 7
3 6

样例输出

2
2
1
1

提示

没有写明提示


题目来源

鸣谢Claris上传

Menuappsclose