HDU6278 - Just h-index 题解

主席树！

题解 #

用主席树我们可以知道在给定区间里的所有数的出现次数。我们可以比较容易的想到一个二分做法：

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;

这种做法的时间复杂度是 $O(n\log n\log n)$ 。足够通过本题，但还有优化的地方。事实上，二分部分可以在树上查询的时候完成。首先我们规定几个变量： $[x,y]$ 为当前询问的区间， $[l,r]$ 为当前在树上查询的区间， $s$ 为 $(r,y]$ 里数字的出现次数。伪代码大概是这样：

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);//(mid,y] 中的数比 mid 大，也就是说答案在右边的区间
    return query(l,mid,s+cnt);//(mid,y] 的数不够多，答案在左边的区间
}

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