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

Problem Description

Given a directed acyclic graph GG with nn vertices and mm edges, and a color sequence a1,a2,⋯ ,ana_1,a_2,\cdots,a_n of length nn, where aia_i denotes the initial color of vertex ii.

Let SiS_i denote the set of all vertices reachable from vertex ii in graph GG (including vertex ii itself).

Now, you need to process qq operations in order. The operations are of the following two types:

  • Given xx and yy, change the color axa_x of vertex xx to yy.
  • Given xx, query the number of distinct colors among all vertices reachable from vertex xx. That is, find the size of the set {aj∣j∈Sx}\{a_j\mid j\in S_x\}.

Input Format

The first line contains two integers 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), representing the number of vertices and the number of edges in the graph, respectively.

The second line contains nn integers a1,a2,⋯ ,ana_1,a_2,\cdots,a_n (1≤ai≤n1 \le a_i \le n), representing the initial color of each vertex.

The next mm lines each contain two integers u,vu,v (1≤u,v≤n1 \le u,v \le n), indicating that there is a directed edge from uu to vv in graph GG. It is guaranteed that graph GG is a directed acyclic graph (DAG) and contains no multiple edges.

The next line contains an integer qq (1≤q≤1.5×1051 \le q \le 1.5\times10^5), representing the total number of operations.

The next qq lines each describe an operation in one of the following two formats:

  • 1 x y: Represents an update operation, changing the color axa_x to yy (1≤x,y≤n1 \le x,y \le n).
  • 2 x: Represents a query operation, querying the number of distinct colors reachable from vertex xx (1≤x≤n1 \le x \le n).

Output Format

For each operation of the second type, output a single line containing an integer representing the answer to the query.

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