1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<bits/stdc++.h>
using std::vector;
typedef vector<int> vi;
typedef long long ll;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
struct psgt{
#define mid ((s+t)>>1)
private:
vi ls,rs,rt;
vector<ll> sum;
int n,V,nt;
public:
psgt(int _n=0,ll _V=0,vi a={}){
n=_n,V=_V,nt=0;
int siz=n*48+100;
ls.resize(siz),rs.resize(siz),sum.resize(siz),rt.resize(n+1);
auto ins=[&](auto ins,int x,int &p,int ver,ll s,ll t) -> void {
p=++nt;ls[p]=ls[ver];rs[p]=rs[ver];sum[p]=sum[ver]+x;
if(s==t)return;
if(x<=mid)ins(ins,x,ls[p],ls[ver],s,mid);
else ins(ins,x,rs[p],rs[ver],mid+1,t);
};
for(int i=1;i<=n;++i)ins(ins,a[i],rt[i],rt[i-1],0,V);
}
ll qry(int L,int R,int l,int r){
auto qr=[&](auto qr,int l,int r,int p,ll s,ll t) -> ll {
if(!p||l>t||s>r)return 0;
if(l<=s&&t<=r)return sum[p];
return qr(qr,l,r,ls[p],s,mid)+qr(qr,l,r,rs[p],mid+1,t);
};return qr(qr,l,r,rt[R],0,V)-qr(qr,l,r,rt[L-1],0,V);
}
#undef mid
};
int main(){
int n=read();
vi a(n+1);
ll sum=0;
for(int i=1;i<=n;++i)sum+=(a[i]=read());
psgt t(n,sum,a);
int q=read();
while(q--){
int l=read(),r=read();
ll X=0,S=0;
for(;;){
ll sm=t.qry(l,r,X+1,S+1);
if(!sm)break;
X=S+1,S+=sm;
}
printf("%lld\n",S+1);
}
return 0;
}
|