982 . 貓咪巡邏隊

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

alvingogo

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

ytp ytp-junior ytp-2025

Description

不好了！夜色鎮最近遭遇了一場前所未有的鼠患！無數老鼠在街道、屋頂、後巷間橫行，讓居民們苦不堪言。為了保護小鎮安全，居民組織了多支巡邏隊，由勇敢的貓咪們日夜守護。你受任為夜色鎮的「貓咪調度官」，需要根據一系列突發事件，靈活地訓練、調度、重編巡邏隊，並記錄貓咪們的戰果。

小鎮共有 $N$ 隻貓咪與 $M$ 隻巡邏隊，每個巡邏隊負責一個街區。每隻貓咪有一個能力值，並隸屬於某個巡邏隊。巡邏隊之間可能互相支援，以應對不同地區的鼠患。

你將依序處理 $Q$ 個事件，依序如下：

  1. 1 u
    補給送達！
    第 $u$ 隻貓咪獲得了一罐營養滿滿的罐罐！該貓咪的能力值 +$1$。

  2. 2 x
    天降罐頭雨！
    第 $x$ 支巡邏隊的所有貓咪能力值全部 +$1$。

  3. 3 u
    全力出擊！
    第 $u$ 隻貓咪發動攻擊，牠一次能抓到與自己能力值數值相同數量的老鼠。

  4. 4 u x
    單兵支援！
    鼠患在某地區升溫，臨時調派第 $u$ 隻貓咪前往協助第 $x$ 支巡邏隊。
    執行後，該貓咪改隸屬於第 $x$ 支巡邏隊，保持能力值不變。

  5. 5 x y
    全隊支援！
    某地區鼠患失控，第 $x$ 支巡邏隊立即全員出動前往支援第 $y$ 支巡邏隊。
    執行後，第 $x$ 支巡邏隊的所有貓咪都將加入第 $y$ 支巡邏隊，每隻貓咪保持能力值不變，$x$ 隊暫時解散（成員歸零）。

Input Format

第一行有三個整數 $N, M, Q$ ，意義如題敘所示。

第二行有 $N$ 個整數 $a_1, a_2, \dots , a_N$ ， $a_i$ 代表第 $i$ 隻貓咪的初始能力值。

第三行有 $N$ 個整數 $x_1, x_2, \dots , x_N$ ， $x_i$ 代表第 $i$ 隻貓咪一開始隸屬於的巡邏隊。

接下來的 $Q$ 行，每行有一個操作，如題敘所示。

  • $1 \le N, M, Q \le 5 \times 10^ 5$
  • $1 \le u \le N$
  • $1 \le x, y \le M, x \neq y$
  • $0 \le a_i \le 10^ 5$
  • $1 \le x_i \le M$

Output Format

對於每個事件 3 ，輸出一個整數，代表抓到的老鼠數量。

對於每個事件 5 ，輸出兩個整數，分別代表第 $x$ 支跟第 $y$ 支巡邏隊在支援前的成員總數。

Sample Input 1

8 10 13
1 4 2 1 3 3 5 2
2 5 1 4 2 5 5 8
2 3
1 7
4 5 3
2 5
5 8 4
3 6
1 1
1 4
4 6 6
5 4 7
2 4
3 5
3 8

Sample Output 1

1 1
4
2 0
3
2

Sample Input 2

4 6 7
1 4 7 2
3 6 1 5
3 3
1 1
4 3 3
1 4
5 3 2
4 2 2
3 2

Sample Output 2

7
2 0
4

Sample Input 3

5 3 8
1 3 2 2 3
1 2 3 3 1
1 3
2 1
3 1
3 4
2 2
1 2
5 1 3
3 5

Sample Output 3

2
2
2 2
4

Hints

以下為在範例中，貓咪們（編號為 $i$ ）的能力值（ $a$ ）與隸屬的巡邏隊（ $x$ ）的變化狀況。

Problem Source

YTP 2025 國中組程式挑戰營 p12

Subtasks

No. Testdata Range Constraints Score
1 38, 45~46 範例測試資料 0
2 0~5, 38, 45~46 $1 \le N, M, Q \le 500$ 2
3 6~15, 39~45, 47~49 沒有事件 2 4
4 16~25, 39~44, 46~49 沒有事件 4 4
5 0~49 無額外限制 15

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 65536 2 5
1 1000 1048576 65536 2 5
2 1000 1048576 65536 2 5
3 1000 1048576 65536 2 5
4 1000 1048576 65536 2 5
5 1000 1048576 65536 2 5
6 1000 1048576 65536 3 5
7 1000 1048576 65536 3 5
8 1000 1048576 65536 3 5
9 1000 1048576 65536 3 5
10 1000 1048576 65536 3 5
11 1000 1048576 65536 3 5
12 1000 1048576 65536 3 5
13 1000 1048576 65536 3 5
14 1000 1048576 65536 3 5
15 1000 1048576 65536 3 5
16 1000 1048576 65536 4 5
17 1000 1048576 65536 4 5
18 1000 1048576 65536 4 5
19 1000 1048576 65536 4 5
20 1000 1048576 65536 4 5
21 1000 1048576 65536 4 5
22 1000 1048576 65536 4 5
23 1000 1048576 65536 4 5
24 1000 1048576 65536 4 5
25 1000 1048576 65536 4 5
26 1000 1048576 65536 5
27 1000 1048576 65536 5
28 1000 1048576 65536 5
29 1000 1048576 65536 5
30 1000 1048576 65536 5
31 1000 1048576 65536 5
32 1000 1048576 65536 5
33 1000 1048576 65536 5
34 1000 1048576 65536 5
35 1000 1048576 65536 5
36 1000 1048576 65536 5
37 1000 1048576 65536 5
38 1000 1048576 65536 1 2 5
39 1000 1048576 65536 3 4 5
40 1000 1048576 65536 3 4 5
41 1000 1048576 65536 3 4 5
42 1000 1048576 65536 3 4 5
43 1000 1048576 65536 3 4 5
44 1000 1048576 65536 3 4 5
45 1000 1048576 65536 1 2 3 5
46 1000 1048576 65536 1 2 4 5
47 1000 1048576 65536 3 4 5
48 1000 1048576 65536 3 4 5
49 1000 1048576 65536 3 4 5
Submit
Back to Top