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
5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5 
 Sample Output2
4
8
8
8      

HINT

#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;
}