题目大意：给定一个长度为$n$的正整数序列$a_i$，$m$次询问，每次询问$[l,r]$，求最小的无法表示成$a_l,a_{l+1},\ldots,a_r$的子集之和的正整数。
数据范围：$1\leq l\leq r\leq n\leq 10^5,1\leq m\leq 10^5,\sum a_i\leq 10^9$
（FJOI考Codechef原题？？？）
这个套路之前学校训练的时候也遇到过，这里又遇到了。。。
我们考虑对于一组询问如何计算。
首先，我们知道$[1,0]$是肯定可以表示出来的（为了方便表示就这样写了）
可以像数学归纳法那样递推，先把所有数从小到大排序，假设$[1,x]$被计算出都是可以表示的，现在又有了一个新的数$v$。
若$v>x+1$，那么$x+1$还是无法表示出来，还是只有$[1,x]$是可以的。
若$v\leq x+1$，那么$[1,x+v]$都是可以表示的。
根据这个规律，我们这样考虑。
设$s_0=0$，每次递推这样做（$i=0,1,2,3,\ldots$）。
计算区间中$\leq s_i+1$的数之和，设为$s_{i+1}$。
反复进行，直到$s_i=s_{i+1}$，也就是无法再扩展这个区间了，答案就是$s_i+1$。
（感性理解一下，应该就是对的）
但是我们需要这样递推多少次呢？
我们发现，$s_i$增长最慢的情况就是$s_0=0,s_1=1,s_2=2,s_3=3,s_4=5,s_5=8,\ldots$，就是斐波那契数列，所以是指数级别增长的，所以在$\log(\sum a_i)$次以内就会停止。
每次计算$\leq s_i+1$的数之和的时候，可以用从小到大将数加入主席树，然后二分一下每次在哪个线段树中计算$[l,r]$中的和就可以了。
时间复杂度为$O(n\log n\log(\sum a_i))$
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
const int N = ;
int n, m, a[N], id[N], root[N], seg[N << ], ls[N << ], rs[N << ], cnt;
inline void pushup(int x){seg[x] = seg[ls[x]] + seg[rs[x]];}
inline void change(int &now, int pre, int L, int R, int pos, int val){
now = ++ cnt; seg[now] = seg[pre]; ls[now] = ls[pre]; rs[now] = rs[pre];
if(L == R){
seg[now] = val;
return;
}
int mid = L + R >> ;
if(pos <= mid) change(ls[now], ls[pre], L, mid, pos, val);
else change(rs[now], rs[pre], mid + , R, pos, val);
pushup(now);
}
inline int query(int x, int L, int R, int l, int r){
if(l <= L && R <= r) return seg[x];
int mid = L + R >> , ans = ;
if(l <= mid) ans += query(ls[x], L, mid, l, r);
if(mid < r) ans += query(rs[x], mid + , R, l, r);
return ans;
}
inline int calc(int l, int r, int v){
int left = , right = n, mid, ans;
while(left <= right){
mid = left + right >> ;
if(a[id[mid]] <= v) ans = mid, left = mid + ;
else right = mid - ;
}
return query(root[ans], , n, l, r);
}
int main(){
scanf("%d", &n);
for(Rint i = ;i <= n;i ++) scanf("%d", a + i), id[i] = i;
sort(id + , id + n + , [](int x, int y) -> bool {return a[x] < a[y];});
for(Rint i = ;i <= n;i ++)
change(root[i], root[i - ], , n, id[i], a[id[i]]);
scanf("%d", &m);
while(m --){
int l, r, s = , tmp = ;
scanf("%d%d", &l, &r);
while(true){
tmp = calc(l, r, s + );
if(s == tmp) break;
s = tmp;
}
printf("%d\n", s + );
}
}
Luogu4587