(luogu4587) 神秘数

发表于 分类于 ， ，

原题链接

思路:

考虑往集合中添数.

假设当前集合中最大值为 \(R\), 和为 \(S\), 可以表示 \([1,S]\) 的所有数.

则此时可以添加进集合中的数范围为 \([1,S+1]\), 可以直接将该值域内所有数全部加入集合当中。若选完后的 \(S\) 大于原来的 \(S\) 则更新，否则说明没有新的符合条件的数， 答案为 \(S+1\).

区间上处理值域直接用主席树即可. 由于选数的过程中 \(S\) 是倍增的， 所以每次查询的时间复杂度是 \(O(log^2n)\).

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cctype>
const int Mn(100500);
const int TL(1), TR(1000000000);
template<typename T> void qrd(T& x) {
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x,Ts&... xs) { //快读
    qrd(x); qrd(xs...);
}

struct Trd {    //主席树节点
    int s;
    int ls, rs;
}tr[Mn*35];
int rts[Mn];    //树根
int newTrd(const Trd& x) {  //开辟新节点
    static int tc(0);
    tr[++tc] = x;
    return tc;
}
void mdf(int& p,int l,int r,int mp) {   //修改
    p = newTrd(tr[p]);
    tr[p].s += mp;
    if(l==r) {
        return;
    }
    int mid((l+r)/2);
    if(mp<=mid) {
        mdf(tr[p].ls,l,mid,mp);
    } else {
        mdf(tr[p].rs,mid+1,r,mp);
    }
}
int qry(int lp,int rp,int l,int r,int qp) { //查询值域前缀和
    if(l==r) {
        return tr[rp].s - tr[lp].s;
    }
    int mid((l+r)/2);
    if(qp<=mid) {
        return qry(tr[lp].ls,tr[rp].ls,l,mid,qp);
    } else {
        return tr[tr[rp].ls].s - tr[tr[lp].ls].s + qry(tr[lp].rs,tr[rp].rs,mid+1,r,qp);
    }
}

int main() {
    int n; qrd(n);
    for(int i(1);i<=n;++i) {
        int a; qrd(a);
        rts[i] = rts[i-1];
        mdf(rts[i],TL,TR,a);
    }
    int m; qrd(m);
    while(m--) {
        int l, r;
        qrd(l,r);
        int sm(0);
        while(true) {
            int tsm = qry(rts[l-1],rts[r],TL,TR,sm+1);
            if(tsm==sm) {   //若无数可选则退出
                break;
            }
            sm = tsm;   //否则更新
        }
        printf("%d\n",sm+1);
    }
    return 0;
}