动态规划、线段树
本文中使用 $V$ 表示背包容量上限。
对于在区间 $[l,r]$ 的物品中取体积至多为 $V$ 的物品的 01 背包，除了直接对区间 $[l,r]$ 做 $r-l+1$ 次时间复杂度 $O(V)$ 的动态规划转移，还有一个方式。
找一个满足 $l \leq mid < r$ 的中点 $mid$，将从 $mid$ 到 $l$ 的物品依次加入并记录每次加入后的动态规划数组，记 $pre_{i,j}$ 为考虑了 $[i,mid]$ 中的每个物品，选择的物品体积至多为 $j$ 能获得的最大价值；同样地，将 $mid+1$ 到 $r$ 的物品依次加入，记 $suf_{i,j}$ 为考虑了 $[mid+1,i]$ 中的每个物品，选择的物品体积至多为 $j$ 能获得的最大价值。
对于求使用体积为 $m$ 的背包，在区间 $[ql,qr]$ 选择物品能获得的最大价值的询问，若询问满足 $l \leq ql \leq mid < ql \leq r$，可以枚举选择 $[ql,mid]$ 中的物品使用的体积 $i$，则选择 $[mid+1,qr]$ 中的物品使用的体积为 $m-i$，因此答案为 $\max\limits_{i=0}^{m} pre_{ql,i} + suf_{qr,m-i}$ 的值。
对区间 $[1,n]$ 建立线段树，对于任意满足 $ql \neq qr$ 的询问区间 $[ql,qr]$ 必定存在一个线段 $[l,r]$，中点为 $mid = \lfloor \frac{l+r}{2} \rfloor$ 且满足 $l \leq ql \leq mid < qr \leq r$，证明：
对于区间 $[1,n]$，所有跨过 $mid$ 的询问会在这里被回答，因此只有 $[ql,qr]$ 完全被 $[1,mid]$ 或 $[mid+1,n]$ 包含时会递归到左子树或者右子树。
推而广之，对于区间 $[l,r]$，递归到这里的所有跨过 $mid$ 的询问会在这里被回答，只有 $[ql,qr]$ 完全被左节点维护的区间或右节点维护的区间包含时才会向下递归。
只有 $ql=qr$ 时询问会递归到叶节点，其余询问都无法递归到叶节点，所以所有满足 $ql \neq qr$ 的询问都会在递归到线段树上某个节点时被回答。
证毕。
线段树只保留结构，用线段树结构查找回答询问的节点，不需要 pushup 和 pushdown 函数。对于非叶节点 $[l,r]$ 维护 $mid-l+1$ 个 $pre$ 数组和 $r-mid$ 个 $suf$ 数组，找到回答询问的节点之后 $O(V)$ 求出答案。
提前判断 $ql=qr$ 的情况，因为区间只包含一个物品，判断物品体积是否 $\leq m$ 即可。
线段树有 $\log n$ 层，每层线段长度之和为 $n$，动态规划数组的大小为 $V$，故空间复杂度为 $O(nV \log n)$，建立线段树的时间复杂度同为 $O(nV \log n)$。单次回答询问需要找到对应线段后拼答案，为 $O(\log n + V)$。
总体时间复杂度 $O(nV \log n + q \log n + qV)$，空间复杂度 $O(nV \log n)$。
#include<bits/stdc++.h>
using namespace std;
constexpr int uim=10'000;
struct Segment{int l,r,**pre,**suf;}s[4'005];
int n,q,a[1'005],b[1'005];
void build(int u,int l,int r){
s[u].l=l,s[u].r=r;
if(l==r) return;
int mid=(l+r)>>1;
s[u].pre=new int*[(mid-l+1)+1];
for(int i=0;i<=mid-l+1;i++){
s[u].pre[i]=new int[10'005];
for(int j=0;j<=10'005-1;j++) s[u].pre[i][j]=0;
}
s[u].suf=new int*[(r-mid)+1];
for(int i=0;i<=r-mid;i++){
s[u].suf[i]=new int[10'005];
for(int j=0;j<=10'005-1;j++) s[u].suf[i][j]=0;
}
for(int i=mid;i>=l;i--){
for(int j=0;j<=uim;j++) s[u].pre[mid-i+1][j]=s[u].pre[mid-i][j];
int *dp=s[u].pre[mid-i+1];
for(int j=uim;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
for(int i=mid+1;i<=r;i++){
for(int j=0;j<=uim;j++) s[u].suf[i-mid][j]=s[u].suf[i-mid-1][j];
int *dp=s[u].suf[i-mid];
for(int j=uim;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
build(u*2,l,mid),build(u*2+1,mid+1,r);
}
int query(int u,int l,int r,int k){
int mid=(s[u].l+s[u].r)>>1;
if(r<=mid) return query(u*2,l,r,k);
if(l>mid) return query(u*2+1,l,r,k);
int ret=0,*pre=s[u].pre[mid-l+1],*suf=s[u].suf[r-mid];
for(int i=0;i<=k;i++) ret=max(ret,pre[i]+suf[k-i]);
return ret;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
build(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;i++){
static int l,r,k,ans;
scanf("%d%d%d",&l,&r,&k);
l=(l+ans)%n+1,r=(r+ans)%n+1;
if(l>r) swap(l,r);
k=(k+ans)%10'000+1;
if(l==r) ans=(a[l]<=k)*b[l];
else ans=query(1,l,r,k);
printf("%d\n",ans);
}
return 0;
}本题时间限制为 2000ms，空间限制 1GB，上面使用数组和指针实现的代码跑了 452ms，使用了 465500KB（约 454.6MB）内存，申请内存那一块的代码还挺长，测一下 vector 版本的代码，如果时间和空间常数都能接受以后就可以直接写 vector 偷懒。
值得一提的是手写 inline max 并没有让代码变快，可能调用函数的次数不够多。
这里放一下 vector 版本代码，它跑了 483ms，使用了 465600KB（约 454.7MB） 内存，几乎和指针版本没区别。
#include<bits/stdc++.h>
using namespace std;
constexpr int uim=10'000;
struct Segment{int l,r;vector<vector<int>> pre,suf;}s[4'005];
int n,q,a[1'005],b[1'005];
void build(int u,int l,int r){
s[u].l=l,s[u].r=r;
if(l==r) return;
int mid=(l+r)>>1;
s[u].pre.resize((mid-l+1)+1,vector<int>(10'005));
s[u].suf.resize((r-mid)+1,vector<int>(10'005));
for(int i=mid;i>=l;i--){
for(int j=0;j<=uim;j++) s[u].pre[mid-i+1][j]=s[u].pre[mid-i][j];
auto &dp=s[u].pre[mid-i+1];
for(int j=uim;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
for(int i=mid+1;i<=r;i++){
for(int j=0;j<=uim;j++) s[u].suf[i-mid][j]=s[u].suf[i-mid-1][j];
auto &dp=s[u].suf[i-mid];
for(int j=uim;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
build(u*2,l,mid),build(u*2+1,mid+1,r);
}
int query(int u,int l,int r,int k){
int mid=(s[u].l+s[u].r)>>1;
if(r<=mid) return query(u*2,l,r,k);
if(l>mid) return query(u*2+1,l,r,k);
auto &pre=s[u].pre[mid-l+1],&suf=s[u].suf[r-mid];
int ret=0;
for(int i=0;i<=k;i++) ret=max(ret,pre[i]+suf[k-i]);
return ret;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
build(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;i++){
static int l,r,k,ans;
scanf("%d%d%d",&l,&r,&k);
l=(l+ans)%n+1,r=(r+ans)%n+1;
if(l>r) swap(l,r);
k=(k+ans)%10'000+1;
if(l==r) ans=(a[l]<=k)*b[l];
else ans=query(1,l,r,k);
printf("%d\n",ans);
}
return 0;
}