D-橘猫的背包问题_2025年华为杯广东工业大学程序设计竞赛（同步赛）

橘猫的背包问题

比赛主页

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

一天，橘猫打算教塑料 01 背包，经过一番惊心动魄的讲解，塑料总算是略懂一二。

在课程结束时，橘猫打算布置 $10^4$ 个 01 背包的作业给塑料，但是造 $10^4$ 个题的数据疑似有点太麻烦了，于是他想了一道新题目：

“橘猫有 $n$ 个价格、价值不等的物品，第 $i$ 个物品的价格为 $p_i$ ，价值为 $v_i$ 。

现在塑料要来购买橘猫的物品。橘猫将所有物品按照编号顺序排成一排，并选定了一段编号区间 $[L,R]$ ，要求塑料只能购买编号在区间 $[L,R]$ 内的物品。

已知塑料带了 $P$ 块钱过来，请你输出他买到的物品的价值之和的最大值。

但为了让你加深对 $01$ 背包的印象，接下来我会给出 $Q$ 次独立的询问，每次询问会给出塑料可以购买的物品的编号区间和塑料携带的金额，对于每次询问，你都要输出他买到的物品的价值之和；

同时，为了让你能够老老实实地做 $Q$ 次 $01$ 背包，本题强制在线。”

塑料写了一个对每个询问区间都跑一遍 $01$ 背包的解法，但是太慢了 TAT，他希望可以尽快得到结果，于是他找到了正在参加校赛的你，请你帮帮他。

输入描述:

本题每个测试点仅有一组测试数据。

第一行输入一个正整数 $n$ ( $1 \leq n \leq 10^3$ )，表示物品的数量；

第二行输入 $n$ 个正整数 $p_1,p_2,...,p_n$ ( $1 \leq p_i \leq 10^4$ )，表示物品的价格；

第三行输入 $n$ 个正整数 $v_1,v_2,...,v_n$ ( $1 \leq v_i \leq 10^5$ )，表示物品的价值；

第四行输入一个正整数 $Q$ ( $1 \leq Q \leq 10^4$ )，表示塑料的个数；

接下来 $Q$ 行，每行给出第 $i$ 个塑料可以挑选的编号区间和他携带的金额的加密值 $iL_i$ , $iR_i$ , $iP_i$ ( $0 \leq iL_i,iR_i \leq n$ , $0 \leq iP_i \leq 10^4$ )。

为了得到真实的 $L_i$ , $R_i$ , $P_i$ ，你需要进行以下解密：

设 $last$ 为上一次询问的答案（第一次询问时 $last = 0$ ），则

$L_i = ((iL_i + last) \bmod n) + 1$

$R_i = ((iR_i + last) \bmod n) + 1$

此时若 $L_i > R_i$ ，则交换 $L_i$ 和 $R_i$ 。

$P_i = ((iP_i + last) \bmod 10000) + 1$

输出描述:

对于每组测试数据的每个询问，输出一个正整数 $x$ ，表示塑料能够购得物品的最大价值。

示例1

输入

复制

输出

复制

3
8
10

备注:

解密后的 $L_i$ , $R_i$ , $P_i$ 如下：

第一组的2 3 7解密后为3 4 8

第二组的1 5 2解密后为4 5 6

第三组的2 5 6解密后为1 4 15。