传送门
这道题真的很水，时间开4s真的没必要，OJ上开1.5s绰绰有余，考试时开O2开1s就够了。
图证:
现在进入正题：
相信100%的人都可以想到折半搜索+尺取，时间复杂度为\(O(q2^{\lfloor\frac{n}{2}\rfloor})\)，约为\(10^9\)规模(每次询问查2次)
如果开3~4s，常数优秀的可以卡过，可我们显然有更优秀的算法。
假设我们预处理了前\(k\)个数的情况，剩下\(n-k\)个在查询的时候进行在线查询，我们每次爆枚后二分，时间复杂度则为\(O(2^k+qk2^{n-k})\)
显然当\(2^k=qk2^{n-k}\)时最优。但上式是超越方程，显然解不出来，所以我们用枚举得到最优解，当\(n=40,q=500\)时\(k=27\),数据规模约为\(3e8\)
当然，我们可以在每次枚举的时候加剪枝，这些东西详见代码。
对预处理的部分我们可以基数排序或者在构造的时候便进行归并排序，都是线性的。
\[\mathfrak{rp=\lim_{TIME \rightarrow NOIP}\frac{1}{NOIP-TIME}}
\]
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;
char k;
bool vis=0;
do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int s,q,a[45],n,cnt;
ll t,sum[45],M,p2[45];
ll va[1<<25],b[1<<25];
double f(int x){return fabs(p2[x]*(s-x+1)*q-p2[s-x]*2);}
void dfs(int n,ll v){
if(v<0)return;
if(sum[n+1]+M<=v){
t+=p2[s-n]*(cnt+1);
return;
}
t+=upper_bound(va,va+cnt+1,v)-va;
for(int i=n+1;i<=s;++i)
dfs(i,v-a[i]);
}
# define W 262143
int main(){
// fre("knapsack");
s=read;q=read;
int k=0;
p2[0]=1;
for(int i=1;i<=s;++i)p2[i]=p2[i-1]*2;
for(int i=1;i<=s;a[i]=read,++i)
if(f(i)<f(k))k=i;
sort(a+1,a+s+1);
if(s-k>25)k=s-25;
n=s-k;if(n<s)reverse(a+n+1,a+s+1);
for(int i=s;i>n;--i)sum[i]=a[i]+sum[i+1];
cnt=1;
for(int i=1;i<=n;++i){
for(int j=0;j<cnt;++j)
va[j|cnt]=va[j]+a[i];
for(int j=0,k=0,t=0;t<(cnt<<1);++t)
if(j==cnt||k!=cnt&&va[k|cnt]<va[j])b[t]=va[k++|cnt];
else b[t]=va[j++];
cnt<<=1;
for(int j=0;j<cnt;++j)va[j]=b[j];
}M=va[--cnt];
for(int i=1;i<=q;++i){
ll l=read-1,r=read;
t=0;dfs(n,l);t=-t;
dfs(n,r);
printf("%lld\n",t);
}
return 0;
}