主席树好题。
本质上是对于前缀的理解与转化。
同题见牛牛的凑数游戏。
实际上那场比赛 T2 和 T3 都是前缀相关的题目。
这题是 T3，看到很容易想到二进制拆分。
稍微推广一下可以发现，对于从小到大的一系列数 \(a_1,a_2,...,a_n\)，处理前缀和 \(pre_1,pre_2,...,pre_n\)；如果存在一个前缀和 \(pre_{i-1}+1<a_i\)，那么无解。
这一点是很好理解的。
本来有一个 \(pre_{i-1}\)（这里满足 \([0,pre_{i-1}]\) 都能被凑出），那么这个 \(a_i\) 的作用就是将 \(pre_{i-1}\) 在数轴上平移了 \(a_i\) 个单位。例如，就是把 \([0,pre_{i-1}]\) 扩展为 \([0,pre_{i-1}]\space\cup\space[a_i,pre_{i-1}+a_i]\)。
这样就很好理解了，存在 \(pre_{i-1}+1<a_i\) 时必定无解。
接下来就可以想，如何使得数组有序？
第一种想法是开一个 multiset 存放当前所有元素。
然后使用莫队算法进行优化。
判断无解只需要开一个线段树，将加入 / 删除元素的过程转化为前缀和上的加减，然后判断区间 \(\min\) 即可。但是复杂度是 \(N \sqrt{N} \log N\) 级别的，无法接受。
好吧，既然不能用 multiset，再想想怎么快速排序求答案？
想到桶排。接着发现加入点的过程长得特别像值域线段树加点。。。
这个问题解决了，那么又如何维护前缀呢？
想到主席树，对于每一个前缀维护一个根就好了。
区间操作消掉左端点以前的影响即可。
转化到这一步，又如何优化这个跑前缀的过程呢？
其实想到整个区间的元素都已经处理到一起了，假设 \([1,p]\) 内元素能凑出的最大元素为 \(res\)。既然 \(res\) 能被凑出，那么可以考虑 \([1,res]\) 内元素凑出的最大元素。如果不满足前面给出的 \(pre_{i-1}+1<a_i\) 条件，就可以直接返回 \(res+1\)。这样的过程类似于倍增，复杂度显然为 \(\log\)。
那么这道题就做完了，复杂度 \(N \log^2 N\)
solve 函数内 if (cur > INF) 是因为牛客上没有和 \(\le 10^9\) 的限制。
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 1e5 + 10, INF = 1e9;
int n, m, cnt, a[N], rot[N]; ll sum[N];
struct Node { int ls, rs; ll val; } t[N << 5];
inline void ins(int &rt, int f, int l, int r, int pos, int val) {
rt = ++cnt; t[rt] = t[f], t[rt].val += val;
if (l == r) return ; int mid = (l + r) >> 1;
if (pos <= mid) ins(t[rt].ls, t[f].ls, l, mid, pos, val);
else ins(t[rt].rs, t[f].rs, mid + 1, r, pos, val);
return ;
}
inline ll query(int rt, int f, int l, int r, int L, int R) {
if (L <= l && r <= R) return t[f].val - t[rt].val;
int mid = (l + r) >> 1; ll res = 0;
if (L <= mid) res += query(t[rt].ls, t[f].ls, l, mid, L, R);
if (R > mid) res += query(t[rt].rs, t[f].rs, mid + 1, r, L, R);
return res;
}
inline void solve() {
int l, r; cin >> l >> r; ll res = 1;
while (1) {
ll cur = query(rot[l - 1], rot[r], 1, INF, 1, (int)res);
// if (cur > INF) { cout << sum[r] - sum[l - 1] + 1 << endl; return ; }
if (cur >= res) res = cur + 1; else break;
}
return cout << res << endl, void();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i], sum[i] = sum[i - 1] + a[i];
for (int i = 1; i <= n; ++i) ins(rot[i], rot[i - 1], 1, INF, a[i], a[i]);
while (m--) solve();
return 0;
}