题目描述
给定两个整数序列 A=(A1,…,AN) 和 B=(B1,…,BN),以及两个正整数序列 V=(V1,…,VN) 和 W=(W1,…,WN)。这四个序列的长度均为 N。
选择两个下标区间(可以为空):为 A 选择 [L,R),为 B 选择 [U,D)。其中,L,R,U,D 是整数,满足 1≤L≤R≤N+1 和 1≤U≤D≤N+1。
令 X 和 Y 分别为这两个区间中出现的数值构成的集合:
X={Ai∣L≤i<R},
Y={Bj∣U≤j<D}.
选择的区间必须满足 X∩Y=∅。换言之,不能有任何数值同时出现在两个区间中。
如果 L=R,则 A 中选出的区间为空,且 X=∅。类似地,如果 U=D,则 B 中选出的区间为空,且 Y=∅。
所选两个区间的得分为
i=L∑R−1Vi+j=U∑D−1Wj.
求所有合法选择中的最大可能得分。
输入格式
输入包含一组或多组测试数据。第一行包含一个整数 T(1≤T≤104),表示测试数据组数。随后依次给出 T 组测试数据,每组格式如下。
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
第一行包含一个整数 N,表示四个序列共同的长度(1≤N≤2×105)。
接下来的四行各包含 N 个整数,分别描述序列 A,B,V,W。
对于每个 i(1≤i≤N),整数 Ai,Bi 满足 1≤Ai,Bi≤N。
对于每个 i(1≤i≤N),整数 Vi,Wi 满足 1≤Vi,Wi≤109。
所有测试数据的 N 之和不超过 6×105。
输出格式
输出 T 行。第 i 行包含第 i 组测试数据的最大可能得分。
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
提示
在第一组测试数据中,可以选择 A 的区间 [1,3) 和 B 的区间 [1,2)。具体来说,令 L=1,R=3,U=1,D=2。这两个区间中的数值集合分别为 {1,2} 和 {3},二者没有交集。得分为
V1+V2+W1=3+4+6=13,
这就是最大可能得分。
在第二组测试数据中,可以为 A 选择空区间,为 B 选择整个区间 [1,4)。具体来说,令 L=2,R=2,U=1,D=4。