33OJ
登录 注册

#P17552. [JAG 2026 Summer Camp #2] Empty Intersection

[JAG 2026 Summer Camp #2] Empty Intersection

题目描述

给定两个整数序列 A=(A1,…,AN)A=(A_1,\ldots,A_N) 和 B=(B1,…,BN)B=(B_1,\ldots,B_N),以及两个正整数序列 V=(V1,…,VN)V=(V_1,\ldots,V_N) 和 W=(W1,…,WN)W=(W_1,\ldots,W_N)。这四个序列的长度均为 NN。

选择两个下标区间(可以为空):为 AA 选择 [L,R)[L,R),为 BB 选择 [U,D)[U,D)。其中,L,R,U,DL,R,U,D 是整数,满足 1≤L≤R≤N+11\le L\le R\le N+1 和 1≤U≤D≤N+11\le U\le D\le N+1。

令 XX 和 YY 分别为这两个区间中出现的数值构成的集合:

X={Ai∣L≤i<R},X=\{A_i\mid L\le i<R\}, Y={Bj∣U≤j<D}.Y=\{B_j\mid U\le j<D\}.

选择的区间必须满足 X∩Y=∅X\cap Y=\varnothing。换言之,不能有任何数值同时出现在两个区间中。

如果 L=RL=R,则 AA 中选出的区间为空,且 X=∅X=\varnothing。类似地,如果 U=DU=D,则 BB 中选出的区间为空,且 Y=∅Y=\varnothing。

所选两个区间的得分为

∑i=LR−1Vi+∑j=UD−1Wj.\sum_{i=L}^{R-1}V_i+\sum_{j=U}^{D-1}W_j.

求所有合法选择中的最大可能得分。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 TT(1≤T≤1041\le T\le 10^4),表示测试数据组数。随后依次给出 TT 组测试数据,每组格式如下。

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
V_1 V_2 ... V_N
W_1 W_2 ... W_N

第一行包含一个整数 NN,表示四个序列共同的长度(1≤N≤2×1051\le N\le 2\times 10^5)。

接下来的四行各包含 NN 个整数,分别描述序列 A,B,V,WA,B,V,W。

对于每个 ii(1≤i≤N1\le i\le N),整数 Ai,BiA_i,B_i 满足 1≤Ai,Bi≤N1\le A_i,B_i\le N。

对于每个 ii(1≤i≤N1\le i\le N),整数 Vi,WiV_i,W_i 满足 1≤Vi,Wi≤1091\le V_i,W_i\le 10^9。

所有测试数据的 NN 之和不超过 6×1056\times 10^5。

输出格式

输出 TT 行。第 ii 行包含第 ii 组测试数据的最大可能得分。

4
3
1 2 3
3 2 1
3 4 5
6 2 1
3
1 1 1
1 1 1
2 3 4
5 5 5
4
1 2 1 3
4 2 4 3
5 6 5 1
4 10 4 10
5
3 1 2 4 3
1 1 2 2 4
1 3 3 2 1
2 2 3 1 1
13
15
33
11

提示

在第一组测试数据中,可以选择 AA 的区间 [1,3)[1,3) 和 BB 的区间 [1,2)[1,2)。具体来说,令 L=1,R=3,U=1,D=2L=1,R=3,U=1,D=2。这两个区间中的数值集合分别为 {1,2}\{1,2\} 和 {3}\{3\},二者没有交集。得分为

V1+V2+W1=3+4+6=13,V_1+V_2+W_1=3+4+6=13,

这就是最大可能得分。

在第二组测试数据中,可以为 AA 选择空区间,为 BB 选择整个区间 [1,4)[1,4)。具体来说,令 L=2,R=2,U=1,D=4L=2,R=2,U=1,D=4。