首先对于数 \(a_i\) 和一个 \(sum\) 内被全部覆盖的区间，若 \(a_i\le sum\)，那么可以将区间覆盖到 \(a_i+sum\)，经典背包，不证明。
那么通过这个可以推出来一种暴力做法，每一次找到一个在 \(l\) 到 \(r\) 小于等于 \(sum\) 的数，将 \(sum\) 加上它，然后再找，初始 \(sum=1\)。
但是这样复杂度明显会非常高，考虑优化这个过程。
利用树状数组维护 \(l\) 到 \(r\) 的所有数，每次查询 \(sum\) 以内的所有数，进行累加，如果 \(sum\) 值发生了改变，再重复这个过程，直到不变为止。
可以很好的发现，每进行一次这个过程，\(sum\) 的值近似 \(\times2\)，所以总共最多进行 \(\log(\max(a_i))\) 次就可以更新完毕，我们称这种过程叫做迭代，迭代是因为处理顺序的原因导致一次答不出来最优解，就进行多次枚举得出答案的过程。
但是复杂度仍然不乐观，复杂度的根源在于每次建树状数组需要花费大量时间，所以考虑能否可持久化，那就可以打可持久化线段树，但是这里选择更简单的方法。
考虑对询问进行前缀和处理，每次需要查询的是 \(1\) 到 \(r\) 小于等于 \(sum\) 的数与 \(1\) 到 \(l-1\) 小于等于 \(sum\) 的数。
那么有很多区间的询问是重合的，就可以离线处理了。
先每次标记询问的位置，然后从前往后遍历整个序列，维护树状数组，每次再更新询问所得到的值，结束遍历后用前缀和处理每次的答案，与之前答案作对比，如果被更新了，那么继续迭代，直到无数值更新后，答案就统计出来了。
时间复杂度：\(O(n\times\log(n)\times\log(\max(a_i)))\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,cnt,f[N],t[N],ans[N],sum[N],bef[N];
struct node
{
int name,data;
}a[N];
int cmp(node fi,node se)
{
return fi.data<se.data;
}
int cmp2(node fi,node se)
{
return fi.name<se.name;
}
struct node2
{
int name,l,r,sum;
}p[N];
int cmp3(node2 fi,node2 se)
{
return fi.r<se.r;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int k)
{
while(x<=cnt)
{
f[x]+=k;
x+=lowbit(x);
}
}
int search(int x)
{
int sum=0;
while(x)
{
sum+=f[x];
x-=lowbit(x);
}
return sum;
}
vector<int>lc[N],rc[N];
void diedai()
{
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++)sum[i]=1;
bool flag=0;
for(int i=1;i<=n;i++)lc[i].clear(),rc[i].clear();
for(int i=1;i<=m;i++)lc[p[i].l-1].push_back(p[i].name);
for(int i=1;i<=m;i++)rc[p[i].r].push_back(p[i].name);
for(int i=1;i<=n;i++)
{
update(a[i].data,t[a[i].data]);
int len=lc[i].size();
for(int j=0;j<len;j++)
{
int l=1,r=cnt;
while(l<r)
{
int mid=(l+r+1)>>1;
if(t[mid]<=p[lc[i][j]].sum)l=mid;
else r=mid-1;
}
sum[lc[i][j]]-=search(l);
}
len=rc[i].size();
for(int j=0;j<len;j++)
{
int l=1,r=cnt;
while(l<r)
{
int mid=(l+r+1)>>1;
if(t[mid]<=p[rc[i][j]].sum)l=mid;
else r=mid-1;
}
sum[rc[i][j]]+=search(l);
}
}
for(int i=1;i<=m;i++)
{
bef[i]=p[i].sum;
if(sum[i]!=p[i].sum)flag=1;
p[i].sum=sum[i];
}
if(flag)diedai();
}
signed main()
{
freopen("niuniunum.in","r",stdin);
freopen("niuniunum.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i].data),a[i].name=i;
sort(a+1,a+1+n,cmp);
int bef=-1;
for(int i=1;i<=n;i++)
{
if(a[i].data!=bef)cnt++,t[cnt]=a[i].data;
bef=a[i].data;
a[i].data=cnt;
}
sort(a+1,a+1+n,cmp2);
for(int i=1;i<=n;i++)update(a[i].data,a[i].data);
scanf("%lld",&m);
for(int i=1;i<=m;i++)
{
p[i].name=i;
scanf("%lld%lld",&p[i].l,&p[i].r);
p[i].sum=1;
}
diedai();
for(int i=1;i<=m;i++)printf("%lld\n",p[i].sum);
return 0;
}
/*
8 6
1 2 3 4 5 17 1 99
1 5
2 5
1 6
1 7
1 8
3 8
*/