链接：https://www.luogu.com.cn/problem/CF500F
这题有两种做法：
\(1\).可将物品线段树分治，这样可以通过
\(2\).可将原序列每隔\(p\)格分块，然后像回滚莫队那样处理每一个以块端点为端点的询问，然后每一个询问可以被拆成两部分，将它们合并即可．
这里给第\(2\)种.
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 20000
using namespace std;
struct node
{
int c,h,t;
};
struct fix
{
int num,dp[8001];
bool operator < (const fix &a)const
{
return num<a.num;
}
};
struct Query
{
int num,x,y;
bool operator < (const Query &a)const
{
return x<a.x;
}
};
fix Q[4001],Q2[4001],tmp;
Query query[40001];
vector<node>P[20001];
node happy[20001];
int p,n,q,block[20001],ans[20001],length,length2;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
void adder(int x)
{
for (int i=0;i<P[x].size();++i)
for (int j=4000;j>=P[x][i].c;--j)
tmp.dp[j]=max(tmp.dp[j],tmp.dp[j-P[x][i].c]+P[x][i].h);
for (int j=1;j<=4000;++j)
tmp.dp[j]=max(tmp.dp[j],tmp.dp[j-1]);
return;
}
int main()
{
n=read(),p=read();
for (int i=1;i<=N;++i)
block[i]=(i-1)/p+1;
for (int i=1;i<=n;++i)
{
happy[i].c=read(),happy[i].h=read(),happy[i].t=read();
P[happy[i].t].push_back(happy[i]);
}
sort(query+1,query+q+1);
for (int i=block[N];i>=1;--i)
{
for (int j=1;j<=4000;++j)
tmp.dp[j]=0;
for (int j=min(i*p,N);j>=(i-1)*p+1;--j)
{
adder(j);
if (P[j].size())
{
Q[++length]=tmp;
Q[length].num=j;
}
}
for (int j=1;j<=4000;++j)
tmp.dp[j]=0;
for (int j=(i-1)*p+1;j<=min(i*p,N);++j)
{
adder(j);
if (P[j].size())
{
Q2[++length2]=tmp;
Q2[length2].num=j;
}
}
}
sort(Q+1,Q+length+1);
sort(Q2+1,Q2+length2+1);
for (int j=1;j<=4000;++j)
Q[0].dp[j]=Q2[0].dp[j]=0;
int x,y,res=0,s1,s2;
q=read();
for (int i=1;i<=q;++i)
{
x=read(),y=read();
res=s1=s2=0;
for (int j=1;j<=length;++j)
if (max(x-p+1,0)<=Q[j].num)
{
s1=j;
break;
}
if (Q[s1].num>min(block[max(x-p+1,0)]*p,N))
s1=0;
for (int j=length2;j>=1;--j)
if (x>=Q2[j].num)
{
s2=j;
break;
}
if (Q[s2].num<(block[x]-1)*p+1)
s2=0;
if (block[max(x-p+1,0)]==block[x])
s2=0;
for (int j=0;j<=y;++j)
res=max(res,Q[s1].dp[j]+Q2[s2].dp[y-j]);
printf("%d\n",res);
}
return 0;
}