题目大意
有n个物品，排成一个序列，每个物品有一个di表示取到i要走的距离，vi表示i的价值。
给m组询问[l,r] ,c,sum，问由[l,r]的di<=c的物品能否凑出sum的价值（每个物品只能用一次）
解法
首先说整体二分。
有m个对于区间的查询[Li,Ri]，考虑当前的二分区间[L,R]，对于所有包含于[L,R]的区间无非
是位于[L,mid]内，[mid+1,R]内和横跨mid三种情况。
前两种情况下递归求解，只需要对于第三种情况求解即可。
本题中，维护f(i,j)表示【用[i,mid]这些物品凑出j的价值所走的最长路】 的最小值
而 g(i,j)表示【用[mid+1,i]这些物品凑出j的价值所走的最长路】 的最小值
这样对于一个横跨mid的区间，只需要判断 min{ max{f(Li,j), g(Ri,sumi-j)} } 是否小于等于ci即可
1 #include2 #include 3 #include 4 5 #define N 20010 6 #define M 100010 7 #define INF 0x7fffffff 8 9 using namespace std;10 11 struct qs12 {13 int l,r,c,sum,ansv,id;14 }a[M],a0[M],a1[M],b[M];15 16 int n,m,v[N],d[N],ansv[M],f[N][101],g[N][101];17 18 void dp(int l,int r)19 {20 int mid=(l+r)>>1;21 for(int i=0;i<=100;i++) g[mid+1][i]=f[mid][i]=INF;22 g[mid+1][0]=0;23 g[mid+1][v[mid+1]]=d[mid+1];24 for(int i=mid+2;i<=r;i++)25 {26 for(int j=0;j<=100;j++) g[i][j]=g[i-1][j];27 for(int j=v[i];j<=100;j++)28 g[i][j] = min(g[i][j], max(g[i-1][j-v[i]], d[i]));29 }30 f[mid][0]=0;31 f[mid][v[mid]]=d[mid];32 for(int i=mid-1;i>=l;i--)33 {34 for(int j=0;j<=100;j++) f[i][j]=f[i+1][j];35 for(int j=v[i];j<=100;j++)36 f[i][j] = min(f[i][j], max(f[i+1][j-v[i]], d[i]));37 }38 }39 40 void solve(int l,int r,int L,int R)41 {42 if(L>R) return;43 if(l==r)44 {45 for(int i=L;i<=R;i++)46 {47 if(d[l]<=a[i].c && a[i].sum==v[l]) a[i].ansv=1;48 else a[i].ansv=0;49 }50 return;51 }52 int mid=(l+r)>>1;53 int tot0=0,tot1=0,tot=0;54 for(int i=L;i<=R;i++)55 {56 if(a[i].r<=mid) a0[++tot0]=a[i];57 else if(a[i].l>mid) a1[++tot1]=a[i];58 else b[++tot]=a[i];59 }60 for(int i=1;i<=tot0;i++) a[L+i-1]=a0[i];61 for(int i=1;i<=tot1;i++) a[L+tot0+i-1]=a1[i];62 dp(l,r);63 for(int i=1;i<=tot;i++)64 {65 int tmp=INF;66 for(int j=0;j<=b[i].sum;j++)67 {68 int t=max(f[b[i].l][j], g[b[i].r][b[i].sum-j]);69 tmp=min(tmp,t);70 }71 if(tmp<=b[i].c) b[i].ansv=1;72 else b[i].ansv=0;73 }74 for(int i=1;i<=tot;i++) a[L+tot0+tot1+i-1]=b[i];75 solve(l,mid,L,L+tot0-1);76 solve(mid+1,r,L+tot0,L+tot0+tot1-1);77 }78 79 int main()80 {81 // freopen("test.txt","r",stdin);82 int T;83 scanf("%d",&T);84 while(T--)85 {86 scanf("%d%d",&n,&m);87 for(int i=1;i<=n;i++) scanf("%d",&v[i]);88 for(int i=1;i<=n;i++) scanf("%d",&d[i]);89 for(int i=1;i<=m;i++)90 {91 scanf("%d%d%d%d",&a[i].l,&a[i].r,&a[i].c,&a[i].sum);92 a[i].id=i;93 }94 solve(1,n,1,m);95 for(int i=1;i<=m;i++) ansv[a[i].id]=a[i].ansv;96 for(int i=1;i<=m;i++) putchar(ansv[i]? '0':'1');97 putchar('\n');98 }99 }