#P4150. [AMPPZ2014]The Staging

    ID: 3366 传统题 1000ms 512MiB 尝试: 59 已通过: 29 难度: 8 上传者: 标签>CF2400提高+/省选-置换循环分解动态 DP普通线段树鸣谢Claris上传

[AMPPZ2014]The Staging

题目描述

在舞台上有 nn 个枪手,第 ii 个枪手瞄准了第 pip_i 个枪手,将于第 uiu_i 秒开枪。一个枪手如果成功开枪, 那么被瞄准的枪手会立刻死亡。

现在给出 qq 次对于 uu 的单点修改操作,请在一开始和每次修改操作后统计出最后存活的枪手个数。

输入格式

第一行一个正整数 nn,表示枪手的个数。

第二行包含 nn 个互不相同的正整数 p1⋯np_{1\cdots n},依次表示每个枪手的目标。

第三行包含 nn 个正整数 u1⋯nu_{1\cdots n},依次表示每个枪手的开枪时间。

接下来一行包含一个正整数 qq,表示修改操作的个数。

接下来 qq 行,每行包含两个正整数 k,vk,v,表示把 uku_k 修改为 vv。

数据保证任何时刻任意两个枪手的开枪时间都不同。

输出格式

第一行包含一个正整数,即在进行修改之前最后存活的枪手个数。

接下来 qq 行,每行包含一个正整数,第 i+1i+1 行输出在第 ii 次修改之后最后存活的枪手个数。

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

数据规模与约定

对于 100%100\% 的数据,1≤n≤2×1051\leq n\leq 2\times 10^5,1≤pi,k≤n1\leq p_i,k\leq n,pi≠ip_i\not =i,1≤ui,v≤1091\leq u_i,v\leq 10^9。

数据保证任何时刻任意两个枪手的开枪时间都不同。