33OJ
登录 注册

#P17499. [ICPC 2026 Wuhan I] I Will Always Remember You

    ID: 20227 远端评测题 10000ms 1024MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>ICPC2026省赛/邀请赛湖北

[ICPC 2026 Wuhan I] I Will Always Remember You

题目描述

给定一个 nn 个点 mm 条边的有向无环图 GG,以及一个长度为 nn 的颜色序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,其中 aia_i 表示点 ii 的初始颜色。

记 SiS_i 表示在图 GG 上从点 ii 出发能够到达的所有点构成的集合(包括点 ii 自身)。

现在需要依次处理 qq 次操作,操作分为以下两种:

  • 给定 xx 和 yy,将点 xx 的颜色 axa_x 修改为 yy。
  • 给定 xx,查询从点 xx 出发能够到达的所有点中,一共有多少种不同的颜色。即求集合 {aj∣j∈Sx}\{a_j\mid j\in S_x\} 的大小。

输入格式

第一行包含两个整数 n,mn,m(1≤n≤1.5×1051 \le n \le 1.5\times10^5,0≤m≤3×1050 \le m \le 3\times10^5),分别表示图的节点数和边数。

第二行包含 nn 个整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n(1≤ai≤n1 \le a_i \le n),表示每个节点的初始颜色。

接下来 mm 行,每行包含两个整数 u,vu,v(1≤u,v≤n1 \le u,v \le n),表示图 GG 中存在一条从 uu 指向 vv 的有向边。保证图 GG 是一个有向无环图,且不存在重边。

接下来一行包含一个整数 qq(1≤q≤1.5×1051 \le q \le 1.5\times10^5),表示操作的总次数。

接下来 qq 行,每行描述一次操作,格式为以下两种之一:

  • 1 x y:表示一次修改操作,将 axa_x 的颜色修改为 yy(1≤x,y≤n1 \le x,y \le n)。
  • 2 x:表示一次查询操作,查询从点 xx(1≤x≤n1 \le x \le n)出发能到达的颜色种类数。

输出格式

对于每个第二种操作,输出一行包含一个整数,表示对应查询的答案。

9 14
8 4 2 3 5 2 2 4 7
3 5
8 9
4 5
5 8
6 8
3 8
1 4
2 9
2 4
2 8
1 3
7 9
1 8
5 7
10
1 6 4
1 3 3
2 1
2 3
1 4 3
1 8 5
1 8 7
2 7
2 2
2 9
6
5
2
5
1