Universal Cup Judging System

Universal Cup

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

Hay $n$ celdas dispuestas en una fila. La celda $i$ tiene un color $c_i$ y contiene una bola de valor $v_i$.

Vas a realizar varios viajes por las celdas. Para cada viaje recibirás un entero $x$ y un conjunto de colores $A = \{a_1, a_2, \cdots, a_k\}$, con $c_x \in A$. El viaje empieza en la celda $x$. Durante el viaje, si estás en la celda $i$, puedes moverte a continuación a la celda $(i - 1)$ o $(i + 1)$. Ten en cuenta que no puedes salir de estas $n$ celdas. Además, en todo momento el color de la celda en la que estás debe pertenecer al conjunto $A$.

Cuando estés en la celda $i$, puedes elegir retirar la bola de esa celda y obtener su valor $v_i$. Como solo hay una bola en cada celda, solo puedes retirar la bola de cada celda una vez.

Tu tarea es procesar $q$ operaciones en orden. Cada operación es de uno de los tres tipos siguientes:

  • $1\ p\ x$: Cambia $c_p$ a $x$.
  • $2\ p\ x$: Cambia $v_p$ a $x$.
  • $3\ x\ k\ a_1\ a_2\ \ldots\ a_k$: Dados la celda inicial $x$ y el conjunto de colores $A = \{a_1, a_2, \cdots, a_k\}$ de un viaje, imagina que lo realizas y calcula el máximo valor total que puedes obtener. Ten en cuenta que este viaje es solo imaginario, por lo que las bolas no se retirarán realmente. Es decir, todas las consultas son independientes.

Entrada

Hay varios casos de prueba. La primera línea de la entrada contiene un entero $T$ que indica el número de casos de prueba. Para cada caso:

La primera línea contiene dos enteros $n$ y $q$ ($1 \le n \le 10^5, 1 \le q \le 10^5$), que indican el número de celdas y el número de operaciones.

La segunda línea contiene $n$ enteros $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le n$), donde $c_i$ es el color inicial de la celda $i$.

La tercera línea contiene $n$ enteros $v_1, v_2, \ldots, v_n$ ($1 \le v_i \le 10^9$), donde $v_i$ es el valor inicial de la bola de la celda $i$.

De las siguientes $q$ líneas, la línea $i$ describe la operación $i$. El formato de entrada es el siguiente:

  • $1\ p\ x$: $1 \le p \le n$ y $1 \le x \le n$.
  • $2\ p\ x$: $1 \le p \le n$ y $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$ y $c_x \in \{a_1,a_2,\cdots,a_k\}$.

Se garantiza que ni la suma de $n$ ni la suma de $q$ de todos los casos de prueba superan $3 \times 10^5$. Además, la suma de $k$ de todos los casos de prueba no supera $10^6$.

Salida

Para cada operación de tipo 3, imprime una línea con un entero que indique el máximo valor total que puedes obtener.

Ejemplos

Entrada 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

Salida 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.