Description
\(n\) 个数的序列，每次询问一个区间，求最小的一个数使得不能用这个区间中的数之和表示。
\(n \leq 10^5, \sum a_i \leq 10^9\)
这两个题一个是权限一个没有真是很方所以我在洛谷交
Solution
第一次用数组写数据结构真短啊
考虑只有一次询问怎么做
把给定的区间内的数排序，从小到大扫一遍。
如果一个数比他之前的数之和至少大了 \(1\) ，那么答案就是和 + 1
否则就可以把\([1,\text{前缀和}]\) 都表示出来（感性理解很容易）
这道题怎么做也就显然了起来。只需要用主席树维护区间中小于等于某个数的数之和即可。流程如下
当前答案是 \(a\)，令 \(S\) 是区间中 \(\leq a\) 的数之和
- 如果 \(S < a\) 则 \(a\) 就是最后的答案
- 否则 让 \(a = S+1\) 然后重复此操作
最开始的时候 \(a=1\)
这样做的话 \(a\) 每次都会翻一倍，所以最后的总复杂度是 \(O(m \log n \log \sum a_i)\)
Code
我写的是动态开点的线段树维护的主席树
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 50000500;
const int L = 1000000000;
int n, m, a[N], cnt;
int root[N], ch[N][2]; ll sum[N];
inline void I (int pre, int now, int l, int r, int val) {
ch[now][0] = ch[pre][0], ch[now][1] = ch[pre][1];
int mid = (l + r) >> 1; sum[now] = sum[pre] + val; if(l == r) return ;
if(val <= mid) ch[now][0] = ++cnt, I(ch[pre][0], ch[now][0], l, mid, val);
else ch[now][1] = ++cnt, I(ch[pre][1], ch[now][1], mid + 1, r, val);
}
inline int Q(int pre, int now, int l, int r, int val) {
if(l == r) return sum[now] - sum[pre]; int mid = (l + r) / 2;
if(val <= mid) return Q(ch[pre][0], ch[now][0], l, mid, val);
else return sum[ch[now][0]] - sum[ch[pre][0]] + Q(ch[pre][1], ch[now][1], mid + 1, r, val);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]); root[i] = ++cnt;
I(root[i - 1], root[i], 1, L, a[i]);
} scanf("%d", &m);
for(int i = 1; i <= m; i++) {
int l, r; scanf("%d %d", &l, &r);
int ans = 1;
int S; while(1) {
S = Q(root[l - 1], root[r], 1, L, ans);
if(S < ans) { printf("%d\n", ans); break ; }
else ans = S + 1;
}
}
return 0;
}