#P10333. 拉开单打

    ID: 9451 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-置换循环分解断环成链FHQ Treap 分裂合并按排名分裂维护顺序统计量增量维护离散化

拉开单打

题目描述

有 nn 名球员,编号为 1,…,n1,\ldots,n。第 ii 名球员的实力为 aia_i,希望与编号为 pip_i 的球员单打。各人的实力互不相同,pip_i 互不相同,且 pi≠ip_i\ne i。

每次计算晋级人数时,所有球员重新进入比赛区。不断从比赛区选出当前实力最强的球员 ii。

  • 若 pip_i 已在晋级区,ii 直接进入晋级区。
  • 否则,ii 与 pip_i 单打,pip_i 被淘汰,ii 进入晋级区。

由于各人的 pip_i 互不相同,所选对手不会已经处于淘汰区。直到比赛区无人时,本轮晋级人数等于晋级区中的球员数。

求初始状态的晋级人数,并在每次永久修改后重新求晋级人数。修改持续生效,重新比赛只重置球员所在区域。

输入格式

第一行两个整数 n,qn,q。接下来 nn 行,第 ii 行两个整数 ai,pia_i,p_i。

接下来 qq 行,每行三个整数 op,x,yop,x,y。

  • op=1op=1,将球员 xx 的实力 axa_x 改为 yy。
  • op=2op=2,交换 pxp_x 与 pyp_y。

输出格式

输出 q+1q+1 行。第一行表示初始晋级人数,之后第 ii 行表示第 i−1i-1 次修改后的晋级人数。

样例 1

6 5
12 2
8 1
11 6
3 5
7 4
10 3
1 3 2
1 2 1
2 1 4
1 1 4
1 6 6
3
3
3
3
4
4

样例 2

10 9
1 3
7 9
6 2
19 10
3 7
13 4
18 5
16 6
11 1
14 8
1 10 20
1 2 15
2 3 9
2 5 6
1 10 8
2 3 4
2 8 5
1 6 4
1 10 17
6
7
7
6
6
5
6
7
7
6

原题另外在下发文件中提供样例 3。

数据范围

n,q≤105n,q\le10^5。修改中的 xx 是球员编号。op=2op=2 时,yy 也是球员编号。op=1op=1 时,yy 表示新实力,原样例和本站评测均可能大于 nn。

原子任务 分值 附加限制
1 20 n,q≤2×103n,q\le2\times10^3
2 30 n,q≤105n,q\le10^5,只有操作 1
3 50 无

原 PDF 题面