Editorial for HDU6278 - Just h-index

Solution #

Using persistent segment tree, we can know the occurrence of all the number in the given interval. We could easily come up with a naive binary search solution which looks like this:

 
int l=0,r=INF;
while(l<=r){
    int mid=(l+r)>>1;
    if(occurrence_of_numbers_bigger_than(mid)>=mid) l=mid+1;
    else r=mid-1;
}
cout<<r<<endl;

Time complexity is $O(q\cdot \log n\cdot \log n)$ , which suffices but we can still optimize it.

In fact, the binary search part could be done during the query on the segment tree. First let’s make some notation: let $[x,y]$ be the interval of the query, $[l,r]$ be the current interval on the segment tree, $s$ be the number of occurrence of numbers ranged in $(r,y]$ . The sudo code of the query function would look like this:

int query(int l,int r,int s){
    int mid=(l+r)>>1;
    int cnt=occurrence_of_number_from_mid_to_r();
    if(cnt+s>=mid+1) return query(mid+1,r,s);//the (mid,y] has more numbers than we need, so the answer must be in the right part
    return query(l,mid,s+cnt);//the numbers in the right part is not enough, so the answer is in the left part.
}

Now the time complexity is $O(n\log n)$ . Please refer to the code in the end for the better understanding of the implementation.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
 
struct PerSegTree {
    vector<int> lson, rson, sum, root;
    int tot;
    PerSegTree(int n) {
        lson = rson = sum = vector<int>(n << 5);
        root = vector<int>(n + 1);
        tot = 0;
    }
    void pushup(int rt) {
        sum[rt] = sum[lson[rt]] + sum[rson[rt]];
    }
    void build(int l, int r, int& rt) {
        rt = ++tot;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, lson[rt]);
        build(mid + 1, r, rson[rt]);
        pushup(rt);
    }
    void update(int pos, int val, int l, int r, int ord, int& rt) {
        rt = ++tot;
        lson[rt] = lson[ord];
        rson[rt] = rson[ord];
        if (l == r) {
            sum[rt] = sum[ord] + val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(pos, val, l, mid, lson[ord], lson[rt]);
        else update(pos, val, mid + 1, r, rson[ord], rson[rt]);
        pushup(rt);
    }
    int query(int pos, int l, int r, int lrt, int rrt) {
        if (l == r) return sum[rrt] - sum[lrt];
        int mid = (l + r) >> 1;
        if (pos <= mid) return sum[rson[rrt]] - sum[rson[lrt]] + query(pos, l, mid, lson[lrt], lson[rrt]);
        return query(pos, mid + 1, r, rson[lrt], rson[rrt]);
    }
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    while(cin>>n>>q){
        PerSegTree tree(n);
        tree.build(1,n,tree.root[0]);
        for1(i,n){
            int x;
            cin>>x;
            tree.update(x,1,1,n,tree.root[i-1],tree.root[i]);
        }
        while(q--){
            int x,y;
            cin>>x>>y;
            int l=0,r=1e5;
            while(l<=r){
                int mid=(l+r)>>1;
                int ans=tree.query(mid,1,n,tree.root[x-1],tree.root[y]);
                if(ans>=mid) l=mid+1;
                else r=mid-1;
            }
            cout<<r<<endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
 
struct PerSegTree {
    vector<int> lson, rson, sum, root;
    int tot;
    PerSegTree(int n) {
        lson = rson = sum = vector<int>(n << 5);
        root = vector<int>(n + 1);
        tot = 0;
    }
    void pushup(int rt) {
        sum[rt] = sum[lson[rt]] + sum[rson[rt]];
    }
    void build(int l, int r, int& rt) {
        rt = ++tot;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, lson[rt]);
        build(mid + 1, r, rson[rt]);
        pushup(rt);
    }
    void update(int pos, int val, int l, int r, int ord, int& rt) {
        rt = ++tot;
        lson[rt] = lson[ord];
        rson[rt] = rson[ord];
        if (l == r) {
            sum[rt] = sum[ord] + val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(pos, val, l, mid, lson[ord], lson[rt]);
        else update(pos, val, mid + 1, r, rson[ord], rson[rt]);
        pushup(rt);
    }
    int query(int l, int r, int old_rt, int rt,int s) {
        if(l==r) return l;
        int mid=(l+r)>>1;
        int cnt=sum[rson[rt]]-sum[rson[old_rt]];
        if(mid<cnt+s) return query(mid+1,r,rson[old_rt],rson[rt],s);
        return query(l,mid,lson[old_rt],lson[rt],s+cnt);
    }
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    while(cin>>n>>q){
        PerSegTree tree(n);
        tree.build(1,n,tree.root[0]);
        for1(i,n){
            int x;
            cin>>x;
            tree.update(x,1,1,n,tree.root[i-1],tree.root[i]);
        }
        while(q--){
            int x,y;
            cin>>x>>y;
            cout<<tree.query(1,n,tree.root[x-1],tree.root[y],0)<<endl;
        }
    }
    return 0;
}