很显然是一个区间背包。
首先考虑线段树维护区间背包，合并两个背包复杂度为 \(O(t^2)\) 的。所以复杂度 \(O(qt^2\log n)\)。无法接受。
线段树维护会出现很多对当前询问无用的状态。考虑把所有询问离线下来一起查询。分治查询经过 \(mid\) 的询问，预处理 \([l,mid],(mid,r]\) 两边到 \(mid\) 的背包，询问即为合并两个背包，而这里的合并因为只用知道合并后 \(t_i\) 上的值，所以复杂度是 \(O(t)\) 的，总复杂度 \(O(nt\log n+qt)\)。
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
using namespace std;
using namespace __gnu_pbds;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
#define intz(x,y) memset((x),(y),sizeof((x)))
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define tup(x) array<int,(x)>
inline ll read(){ll x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;
}
//void write(int x){cout<<x<<' ';}
//void write(pii x){cout<<"P("<<x.fi<<','<<x.se<<")\n";}
//void write(vector<auto>x){for(auto i:x)write(i);cout<<'\n';}
//void write(auto *a,int l,int r){for(int i=l;i<=r;i++)write(a[i]);cout<<'\n';}
inline ll lowbit(ll x){return x&-x;}
inline int pcount(ll x){for(int i=0,res=0;;res+=(x>>i)&1,i++)if(i>60)return res;
}//struct mt{
// ll v;
// mt(){v=0;}
// mt(int x){this->v=x;}
// inline mt operator+(mt x){return {(v+x.v)%mod};}
// inline mt operator-(mt x){return {(v+mod-x.v)%mod};}
// inline mt operator*(mt x){return {1ll*v*x.v%mod};}
//};
//inline void add(mt &x,mt y){x=x+y;}
//mt qp(mt x,int y){mt res(1);for(;y;x=x*x,y>>=1)if(y&1)res=res*x;return res;}
const int N=4e4+5,M=2e5+5,T=205;
struct node{int l,r,t,id;};
int h[N],w[N],f[N][T],g[N][T],ans[M],n,m;vector<node>a;
void solve(int l,int r,vector<node>q){if(!q.size())return;if(l==r){for(node i:q)if(i.t>=h[l])ans[i.id]=w[l];return;}int mid=l+r>>1;vector<node>L,R,a;for(node i:q)if(i.l<=mid&&i.r>mid)a.pb(i);else (i.r<=mid?L:R).pb(i);solve(l,mid,L),solve(mid+1,r,R);for(int i=mid;i>=l;i--){for(int j=200;j;j--)f[i][j]=(i<mid?f[i+1][j]:0);for(int j=200;j>=h[i];j--)f[i][j]=max(f[i][j],f[i][j-h[i]]+w[i]);}for(int i=mid+1;i<=r;i++){for(int j=200;j;j--)g[i][j]=(i>mid+1?g[i-1][j]:0);for(int j=200;j>=h[i];j--)g[i][j]=max(g[i][j],g[i][j-h[i]]+w[i]);}for(node t:a)for(int i=0;i<=t.t;i++)ans[t.id]=max(ans[t.id],f[t.l][i]+g[t.r][t.t-i]);
}
inline void UesugiErii(){cin>>n>>m;a.resize(m);for(int i=1;i<=n;i++)cin>>h[i];for(int i=1;i<=n;i++)cin>>w[i];for(int i=0;i<m;i++)cin>>a[i].l>>a[i].r>>a[i].t,a[i].id=i+1;solve(1,n,a);for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}
signed main(){//IO();cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}