Universal Cup Judging System

Universal Cup

Time Limit: 5 s Memory Limit: 1024 MB Total points: 100
Statistics

$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$ を得ることを選べます。各マスにはボールが $1$ つしかないため、各マスからボールを取り除けるのは $1$ 回だけです。

あなたの課題は $q$ 回の操作を順に処理することです。各操作は次の $3$ 種類のいずれかです:

  • $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$ が与えられます。各テストケースについて:

最初の行には、マスの数と操作の数を表す $2$ 個の整数 $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$ 番目のマスの初期の色です。

$3$ 行目には $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$ 行に出力してください。

入出力例

入力 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.