bzoj 4408 [Fjoi 2016]神秘数主席树

本文主要是介绍bzoj 4408 [Fjoi 2016]神秘数主席树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，

1 = 1

2 = 1+1

3 = 1+1+1

4 = 4

5 = 4+1

6 = 4+1+1

7 = 4+1+1+1

8无法表示为集合S的子集的和，故集合S的神秘数为8。

现给定n个正整数a[1]..a[n]，m个询问，每次询问给定一个区间l,r，求由a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。

Input

第一行一个整数n，表示数字个数。
第二行n个整数，从1编号。
第三行一个整数m，表示询问个数。
以下m行，每行一对整数l,r，表示一个询问。

Output

对于每个询问，输出一行对应的答案。

Sample Input

1 2 4 9 10

1 1

1 2

1 3

1 4

1 5
Sample Output

8
HINT

对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9

传送门
这题厉害了……
对于一个序列，假设我们把它排序了，当前位置为x，之前的前缀和是S，
那么显然S+1 < x的时候，S+1就是神秘数，不然就可以后推。
然而这题是多个区间询问……于是就不会啦= v =

题解还是挺神的。。
对于一个序列，除了排序还可以酱紫做。。
首先设置一个ans=1，
每次求出<=ans的所有数的和，假设这个和为get，
那么当get < ans的时候，ans就是解了，
不然就把ans更新为get+1.
区间求<=ans的数的和？用个主席树就ok了。。
而比较nb的是这个循环的次数……
次数似乎不会太多……听说是 $log(\sum a[i])$ 次？
太神啦。。

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,Tcnt,root[N],a[N];
struct CT{int l,r,num;}ct[N*40];
void insert(int &u,int num,int L,int R){ct[++Tcnt]=ct[u];u=Tcnt,ct[u].num+=num;if (L==R) return;int mid=(L+R)>>1;if (num<=mid) insert(ct[u].l,num,L,mid);else insert(ct[u].r,num,mid+1,R);
}
int query(int ll,int rr,int num,int L,int R){if (L==R) return ct[rr].num-ct[ll].num;int mid=(L+R)>>1;if (num<=mid) return query(ct[ll].l,ct[rr].l,num,L,mid);else return ct[ct[rr].l].num-ct[ct[ll].l].num+query(ct[ll].r,ct[rr].r,num,mid+1,R);
}
int main(){scanf("%d",&n);int tot=0;for (int i=1;i<=n;i++)scanf("%d",&a[i]),tot+=a[i];root[0]=0;for (int i=1;i<=n;i++)root[i]=root[i-1],insert(root[i],a[i],1,tot);int Q,l,r;scanf("%d",&Q);while (Q--){scanf("%d%d",&l,&r);int ans=1,get;while (1){get=query(root[l-1],root[r],ans,1,tot);if (get<ans) break;ans=get+1;}printf("%d\n",ans);}return 0;
}