Universal Cup Judging System

Universal Cup

حد الوقت: 5 s حد الذاكرة: 1024 MB مجموع النقاط: 100
الإحصائيات

$n$개의 칸이 한 줄로 배열되어 있습니다. $i$번째 칸은 색 $c_i$이며 값이 $v_i$인 공 하나가 들어 있습니다.

여러분은 이 칸들에서 여러 번 여행하려고 합니다. 각 여행마다 정수 $x$와 색 집합 $A = \{a_1, a_2, \cdots, a_k\}$가 주어지며 $c_x \in A$입니다. 여행은 칸 $x$에서 시작합니다. 여행 중 칸 $i$에 있다면 다음에는 칸 $(i - 1)$ 또는 $(i + 1)$로 이동할 수 있습니다. 이 $n$개의 칸 밖으로 나갈 수 없음에 유의하세요. 또한 어느 시점이든 현재 있는 칸의 색은 집합 $A$에 속해야 합니다.

칸 $i$에 있을 때 그 칸의 공을 제거하고 그 값 $v_i$를 얻는 것을 선택할 수 있습니다. 각 칸에는 공이 하나뿐이므로 각 칸에서 공을 제거하는 것은 한 번만 가능합니다.

여러분의 과제는 $q$개의 연산을 순서대로 처리하는 것입니다. 각 연산은 다음 세 유형 중 하나입니다:

  • $1\ p\ x$: $c_p$를 $x$로 바꿉니다.
  • $2\ p\ x$: $v_p$를 $x$로 바꿉니다.
  • $3\ x\ k\ a_1\ a_2\ \ldots\ a_k$: 여행의 시작 칸 $x$와 색 집합 $A = \{a_1, a_2, \cdots, a_k\}$가 주어집니다. 이 여행을 한다고 가정하고 얻을 수 있는 총값의 최댓값을 계산하세요. 여행은 가정일 뿐이므로 공이 실제로 제거되지는 않음에 유의하세요. 즉, 모든 쿼리는 서로 독립적입니다.

입력

여러 테스트 케이스가 있습니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$가 주어집니다. 각 테스트 케이스에 대해:

첫 번째 줄에는 칸의 개수와 연산의 개수를 나타내는 두 정수 $n$과 $q$가 주어집니다 ($1 \le n \le 10^5, 1 \le q \le 10^5$).

두 번째 줄에는 $n$개의 정수 $c_1, c_2, \ldots, c_n$가 주어집니다 ($1 \le c_i \le n$). $c_i$는 $i$번째 칸의 초기 색입니다.

세 번째 줄에는 $n$개의 정수 $v_1, v_2, \ldots, v_n$가 주어집니다 ($1 \le v_i \le 10^9$). $v_i$는 $i$번째 칸의 공의 초기 값입니다.

다음 $q$개의 줄 중 $i$번째 줄에는 $i$번째 연산이 주어집니다. 입력 형식은 다음과 같습니다:

  • $1\ p\ x$: $1 \le p \le n$ 및 $1 \le x \le n$.
  • $2\ p\ x$: $1 \le p \le n$ 및 $1 \le x \le 10^9$.
  • $3\ x\ k\ a_1\ a_2\ \ldots\ a_k$: $1 \le x \le n$, $1 \le a_1 < a_2 < \ldots < a_k \le n$ 및 $c_x \in \{a_1,a_2,\cdots,a_k\}$.

모든 테스트 케이스에서 $n$의 합과 $q$의 합은 각각 $3 \times 10^5$를 넘지 않음이 보장됩니다. 또한 모든 테스트 케이스에서 $k$의 합은 $10^6$을 넘지 않습니다.

출력

유형 3의 각 연산에 대해 얻을 수 있는 총값의 최댓값을 나타내는 정수 하나를 한 줄에 출력하세요.

예제

입력 1

2
5 10
1 2 3 1 2
1 10 100 1000 10000
3 3 1 3
3 3 2 2 3
2 5 20000
2 3 200
3 3 2 1 3
3 3 3 1 2 3
1 3 4
2 1 100000
1 2 2
3 1 2 1 2
4 1
1 2 3 4
1000000 1000000 1000000 1000000
3 4 4 1 2 3 4

출력 1

100
110
1200
21211
100010
4000000

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.