考虑暴力怎么写
首先将所有数排序，之后一个一个加入，设当前加入的数的和为(sum)，要加入的数为(x)
结论就是，如果(x>sum+1)，那么最小的不能表示的数就是(sum+1)，否则就另(sum=sum+x)，继续加入
正确性显然，因为当前加入的数的和为(sum)，所以能表示出来的数的范围在([0,sum])，想要表示出(sum+1)，就要从这个范围内找到一个数和(x)相加等于(x)，显然这个数是(sum+1-x)；如果(sum+1)不能被表示出来，就说明(sum+1-x)不能在这个范围内取到，即(sum+1-x<0)，也就是(x>sum+1)
考虑优化这个暴力
我们设排序之后的前(i)个数的和为(pre_i)，(x>sum+1)就能表示成(pre_i-pre_{i-1}>pre_{i-1}+1)，也就是(pre_i>2 imes pre_{i-1}+1)
设当前加入的数的和为(sum)，我们用一个主席树找到第一个满足大于(2 imes sum+1)的前缀和，记为(v)，同时查出这个前缀和的排名
再利用主席树查一波这个排名减一的前缀和，记为(g)，如果满足(2 imes g+1<v)，那么答案就是(g+1)；否则就另(sum=v)，继续查询
复杂度是(O(mlog nlog sum a))
代码
#include<bits/stdc++.h>
#define re register
#define min(a,b) ((a)<(b)?(a):(b))
#pragma GCC optimize(3)
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("Ofast,no-stack-protector")
#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1<<15,stdin),S==T)?EOF:*S++)
char BB[1<<18],*S=BB,*T=BB;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=1e5+5;
const int M=maxn*25;
int n,m,sz,a[maxn],b[maxn],rt[maxn],pre[maxn],rk,sum,g,cnt;
int l[M],r[M],d[M],s[M];
inline int find(int x) {
int l=1,r=sz;
while(l<=r) {
int mid=l+r>>1;
if(b[mid]==x) return mid;
if(b[mid]<x) l=mid+1;else r=mid-1;
}
return 0;
}
int ins(int pre,int x,int y,int pos,int v) {
int now=++cnt;d[now]=d[pre]+v;s[now]=s[pre]+1;
if(x==y) return now;
l[now]=l[pre],r[now]=r[pre];
int mid=x+y>>1;
if(pos<=mid) l[now]=ins(l[pre],x,mid,pos,v);
else r[now]=ins(r[pre],mid+1,y,pos,v);
return now;
}
int getmin(int A,int B,int x,int y) {
if(x==y) return b[x];
int mid=x+y>>1;
if(d[l[B]]-d[l[A]]) return getmin(l[A],l[B],x,mid);
return getmin(r[A],r[B],mid+1,y);
}
void query(int A,int B,int x,int y,int k) {
if(x==y) {
int q=k/b[x];
if(k%b[x]) q++;q=min(q,s[B]-s[A]);
rk+=q,sum+=q*b[x];
return;
}
int mid=x+y>>1;
if(k<=d[l[B]]-d[l[A]]) query(l[A],l[B],x,mid,k);
else {
rk+=s[l[B]]-s[l[A]];sum+=d[l[B]]-d[l[A]];
query(r[A],r[B],mid+1,y,k-d[l[B]]+d[l[A]]);
}
}
int get(int A,int B,int x,int y,int k) {
if(x==y) return k*b[x];
int mid=x+y>>1;
if(k<=s[l[B]]-s[l[A]]) return get(l[A],l[B],x,mid,k);
return d[l[B]]-d[l[A]]+get(r[A],r[B],mid+1,y,k-s[l[B]]+s[l[A]]);
}
int main() {
n=read();
for(re int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
std::sort(b+1,b+n+1);sz=std::unique(b+1,b+n+1)-b-1;
for(re int i=1;i<=n;i++) rt[i]=ins(rt[i-1],1,sz,find(a[i]),a[i]);
for(re int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
m=read();int x,y,v,w;
while(m--) {
x=read(),y=read();v=getmin(rt[x-1],rt[y],1,sz);w=pre[y]-pre[x-1];
if(v!=1) {puts("1");continue;}
while(v<w) {
rk=0;sum=0;query(rt[x-1],rt[y],1,sz,2*v+2);
if(sum<=2*v+1) {printf("%d
",w+1);break;}
g=get(rt[x-1],rt[y],1,sz,rk-1);
if(g*2+1<sum) {printf("%d
",g+1);break;}
v=sum;
}
if(v==w) printf("%d
",w+1);
}
return 0;
}