HDU – 4417 Super Mario 主席树+二分

Super Mario 主席树+二分

 Source

HDU - 4417

My Solution

题意：给出一个长度为n(1<=n<=1e5)的数组，m(1<=m<=1e5)次询问，每次询问在区间[L,R]中小于等于X的数的个数。

主席树+二分

朴素的主席树是查询区间第k大(从小到大第k大)，所以只需要在每次询问的时候二分的找出在此区间里比X大的最小的数的大小，比如这个值为y(初始化为-1)，则答案为y-1，即把这个比X大的数去掉(因为X可能不止一个，所以要这样处理)，此外如果y未被刷新则说明X是这个区间最大的数了 此时y = R-L+1。                       

所以时间复杂度 O(n*logn*logn)

空间复杂度 O(n*logn)

应该还有更直接的时间复杂度为O(n*logn)的算法 ^_^

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;

//Chairman_Tree
int tot, sz;
int a[MAXN], b[MAXN], root[20*MAXN], ls[20*MAXN], rs[20*MAXN], sum[20*MAXN];

inline void _build(int &o, int l, int r){
    o = ++ tot;
    sum[o] = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    _build(ls[o], l, mid);
    _build(rs[o], mid + 1, r);
}

inline void update(int &o, int l, int r, int last, int p){
    o = ++ tot;
    ls[o] = ls[last];
    rs[o] = rs[last];
    sum[o] = sum[last] + 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(p <= mid) update(ls[o], l, mid, ls[last], p); else update(rs[o], mid + 1, r, rs[last], p); } inline int _query(int ss, int tt, int l, int r, int k){ if(l == r) return l; int mid = (l + r) >> 1;
    int  cnt = sum[ls[tt]] - sum[ls[ss]];
    if(k <= cnt) return _query(ls[ss], ls[tt], l, mid, k); else return _query(rs[ss], rs[tt], mid + 1, r, k - cnt); } int main() { #ifdef LOCAL freopen("b.txt", "r", stdin); //freopen("b.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int T, n, m, i, ql, qr, x, ind, kase = 1; cin >> T;
    while(T--){
        cout << "Case " << kase << ":n"; kase++; cin >> n >> m;
        for(i = 1; i <= n; i++){ cin >> a[i];
            b[i] = a[i];
        }
        sort(b + 1, b + n + 1);
        sz = unique(b + 1, b + n + 1) - (b + 1);
        for(i = 1; i <= n; i++){
            a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b; //It is based on 1~n..
        }
        tot = 0;
        _build(root[0], 1, sz);
        for(i = 1; i <= n; i++){ update(root[i], 1, sz, root[i-1], a[i]); } int l, r, mid, ansx, ansind; while(m--){ cin >> ql >> qr >> x;
            ql++, qr++;
            l = 0, r = qr - ql + 1 + 1;
            ansind = -1;
            while(l + 1 < r){ mid = (l + r) >> 1;
                ind = _query(root[ql - 1], root[qr], 1, sz, mid);
                if(b[ind] <= x){
                    l = mid;
                }
                else{
                    r = mid;
                    ansind = mid;
                }
            }
            if(ansind == -1) cout << qr - ql + 1 << "n";
            else cout << ansind - 1 << "n";
        }

    }
    return 0;
}