Description 在Byteland一共有n家商店，编号依次为1到n。每家商店只会卖一种物品，其中第i家商店的物品单价为vi，且它到Byteasar的家的距离为di Byteasar每天都会进行一次购物，第i天他会选择一个区间[li,ri]，并给自己设定一个距离上限ci，然后他会在编号在该区间内每家到自己家的距离不超过ci的商店购买最多一件物品，当然他也可以选择什么都不买。回家之后，Byteasar会把今天购物所花的钱的总数sumi记录在账本上。 Byteasar的数学不好，他可能会把花的钱记错。 请写一个程序，帮助Byteasar判断每条记录是否一定是错的。 注意：记多或者记少都算记错。 Input 输入的第一行包含一个正整数T(1≤T≤10)，表示测试数据的组数。 对于每组数据，第一行包含两个正整数n,m(1≤n≤20000,1≤m≤100000)，表示商店的个数和记录的个数。 第二行包含n个正整数vi(1<=vi<=100)，依次表示每家商店的物品的单价。 第三行包含n个正整数di(1<=di<=10^9)，依次表示每家商店到Byteasar的家的距离。 接下来m行，每行包含四个整数li,ri,ci,sumi表示一条记录 (1<=li<=ri<=n,1<=ci<=10^9,1<=sumi<=100) Output 对于每组数据，输出一行m个字符，依次回答每个询问。如果一定记错了，请输出’1’，否则输出’0’。 Sample Input 2 3 3 3 3 3 2 4 3 3 3 5 3 3 3 3 1 2 3 1 3 5 4 5 1 2 4 2 1 8 9 2 1 1 5 1 3 4 4 1 5 1 5 3 5 1 3 5 1 Sample Output 011 1101 Solution 整体二分，对1~n这n家商店二分，对于一个区间[L,R]，将操作按ri<=mid和li>mid分到[L,mid]和[mid+1,R]中，所以只需要考虑li<=mid< ri的操作，用f[i][j]表示在区间[i,mid]这些商店中购买价值为j的物品所选择的商店中距离最大值的最小值，用g[i][j]表示在区间[mid+1,i]这些商店中购买价值为j的物品所选择的商店中距离最大值的最小值，对于每个li<=mid< ri的操作，可以用类似01背包的方法在O(100*(ri-li+1))的复杂度中求出f数组和g数组，那么第i个操作是否合法就是看是否存在一个j(0<=j<=sum[i])，使得max( f[li][j], g[ri][sum[i]-j]] )<=ci，如果存在说明这个操作可能没错，如果不存在说明这个操作一定是错的，这样做的总时间复杂度是O(100(nlogn+m)+mlogn) Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 22222 #define maxm 111111 int T,n,m,v[maxn],d[maxn],l[maxm],r[maxm],c[maxm],sum[maxm]; int ans[maxm],a[maxm],b[maxm],f[maxn][111],g[maxn][111]; void Solve(int L,int R,int ll,int rr) { if(ll>rr)return ; if(L==R) { for(int i=ll;i<=rr;i++) ans[a[i]]=v[L]==sum[a[i]]&&d[L]<=c[a[i]]; return ; } int mid=(L+R)>>1,p1=ll,p2=rr,p3=0; for(int i=ll;i<=rr;i++) { if(r[a[i]]<=mid)a[p1++]=a[i]; else if(l[a[i]]>mid)b[p2--]=a[i]; else b[p3++]=a[i]; } for(int i=p2+1;i<=rr;i++)a[i]=b[i]; if(p3) { f[mid][0]=g[mid+1][0]=0; for(int i=1;i<=100;i++)f[mid][i]=g[mid+1][i]=INF; f[mid][v[mid]]=d[mid],g[mid+1][v[mid+1]]=d[mid+1]; for(int i=mid-1;i>=L;i--) { for(int j=v[i];j<=100;j++) f[i][j]=min(f[i+1][j],max(f[i+1][j-v[i]],d[i])); for(int j=v[i]-1;j>=0;j--) f[i][j]=f[i+1][j]; } for(int i=mid+2;i<=R;i++) { for(int j=v[i];j<=100;j++) g[i][j]=min(g[i-1][j],max(g[i-1][j-v[i]],d[i])); for(int j=v[i]-1;j>=0;j--) g[i][j]=g[i-1][j]; } for(int i=0;i<p3;i++) for(int j=0;j<=sum[b[i]];j++) ans[b[i]]|=max(f[l[b[i]]][j],g[r[b[i]]][sum[b[i]]-j])<=c[b[i]]; } Solve(L,mid,ll,p1-1); Solve(mid+1,R,p2+1,rr); } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&v[i]); for(int i=1;i<=n;i++)scanf("%d",&d[i]); for(int i=1;i<=m;i++)scanf("%d%d%d%d",&l[i],&r[i],&c[i],&sum[i]); for(int i=1;i<=m;i++)a[i]=i,ans[i]=0; Solve(1,n,1,m); for(int i=1;i<=m;i++)printf("%d",ans[i]^1); printf("\n"); } return 0; }