题解 P1997 【faebdc的烦恼】

· · 题解

这是一篇主席树的题解。

我们思考主席树的本质，其实就是可以刨出一个区间l,r让我们可以在树高复杂度log的基础上进行一波常规线段树不能进行的、权值查找操作。那么由于主席树本质上是一棵权值线段树，所以直接return的val一定是最小的（只要我们保证先查找左子树）。

以上是老生常谈，是我从自己以前整理过的笔记扒拉出来的。

而对于这道题，我们考虑二分。为什么满足二分的性质呢？比较显然的是，如果我们通过查找出现次数为k的数，发现访问的值为NULL，那么对于任何k+x(x \in \mathbb{N})，访问的val都将会是NULL。

那么我们就可以二分实现(这份代码有81pts~with TLE*2)

int build(const int &l, const int &r){
    register int rt = ++ cnt ;
    sum[rt] = 0 ;
    if(l < r){
        register int mid = (l + r) >> 1 ;
        L[rt] = build(l, mid), R[rt] = build(mid + 1, r) ;
    }
    return rt;
}
int update(const int &last, const int &l, const int &r, const int &x){
    register int rt = ++ cnt ;
    sum[rt] = sum[last] + 1, R[rt] = R[last], L[rt] = L[last] ;
    if (l < r){
        register int mid = (l + r) >> 1 ;
        if (x <= mid) L[rt] = update(L[last], l, mid, x) ;
        else  R[rt] = update(R[last], mid + 1, r, x) ;
    }
    return rt ;
}
int query(const int &Left,const int &Right,const int &l, const int &r, const int &k){
    if (l == r) return aft[l] ; 
    register int mid = (l + r) >> 1, qwq ;
    if (sum[Right] - sum[Left] < k) return -1 ;
    int x = sum[L[Right]] - sum[L[Left]], y = sum[R[Right]] - sum[R[Left]] ;
    if (x >= k) 
        if ((qwq = query(L[Left], L[Right], l, mid, k)) > 0) return qwq ;
    if (y >= k) 
        if ((qwq = query(R[Left], R[Right], mid + 1, r, k)) > 0) return qwq ;
    return -1 ;
}
int main(){
    cin >> N >> M; for (i = 1; i <= N; i ++)  base[i] = qr() + ADD, aft[i] = base[i] ;
    sort (aft + 1, aft + N + 1), Len = unique(aft + 1, aft + N + 1) - (aft + 1), T[0] = build(1, Len) ;
    for (i = 1; i <= N; i ++) pos = lower_bound(aft + 1, aft + Len + 1, base[i]) - aft, T[i] = update(T[i - 1], 1, Len, pos) ;
    for (i = 1; i <= M; i ++){
        scanf("%d%d", &a, &b) ;
        register int l = 1, r = b - a + 1, ans = 1 ;
        while (l <= r){
            register int mid = (l + r) >> 1 ;
            if (query(T[a - 1], T[b], 1, Len, mid) > 0) ans = mid, l = mid + 1 ; 
            else r = mid - 1 ;
        }
        printf("%d\n", ans) ;
    }
}

但事实上，我们认知中的主席树上二分的复杂度应该是\Theta(q \log ^2n)，其中一个\log用来二分，一个\log用来查找。但事实上我们这么写，其复杂度并不是对的。因为我们为了防止漏掉可行解，每次需要查询两棵子树，而查询两棵子树的复杂度，最坏情况下却是单次\Theta(2^n)的。那么复杂度就会完全爆炸，以至于最后我不得不写两个subtask用暴力去AC（事实上，这种情况下的主席树是没有暴力快的）。

换句话说，这复杂度特么根本不对……

那么接下来是一个剪枝，由巨佬乖≮闹√€提出，并且时间效率十分的高。

大体思路就是，考虑对于主席树上的每一个点维护一个max一个min，记录区间内单个数值出现的最大次数和最小次数，那么我们在check的时候就可以直接用这种方式判——如果r版本的主席树内出现的最大次数减去l-1版本内出现的数的最小次数k<q（q是二分出的val），那么一定不满足。

事实上，这种剪枝并不是最优性剪枝，但是通过此题足矣：

#include <cstdio>
#include <iostream>
#include <algorithm>

#define il inline
#define ADD 393216
#define rr register
#define MAXN 100073

using namespace std ;
int a, b, c, pos, N, base[MAXN], mx[(MAXN << 5) + 1], mn[(MAXN << 5) + 1], aft[MAXN], M, i ;
int cnt, Len, T[(MAXN << 5) + 1], L[(MAXN << 5) + 1], R[(MAXN << 5) + 1], sum[(MAXN << 5) + 1] ;

il int qr(){
    register int k = 0, f = 1 ; char c = getchar() ;
    while(!isdigit(c)){ if (c == '-') f = -1 ; c = getchar() ; }
    while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ;
    return k * f ;
}
int update(const int &last, const int &l, const int &r, const int &x){
    register int rt = ++ cnt, mid ;
    sum[rt] = sum[last] + 1, R[rt] = R[last], L[rt] = L[last] ;
    if (l == r){
        mx[rt] = mn[rt] = sum[rt] ; 
        return rt ;
    }
    mid = (l + r) >> 1 ;
    if (x <= mid) L[rt] = update(L[last], l, mid, x) ;
    else  R[rt] = update(R[last], mid + 1, r, x) ;
    mn[rt] = min(mn[L[rt]], mn[R[rt]]), mx[rt] = max(mx[L[rt]], mx[R[rt]]) ;
    return rt ;
}
bool query(const int &Left,const int &Right,const int &l, const int &r, const int &k){
    if (l == r) return 1 ; rr int mid = (l + r) >> 1, qwq ;
    if (mx[L[Right]] - mn[L[Left]] >= k && query(L[Left], L[Right], l, mid, k)) return 1 ;
    if (mx[R[Right]] - mn[R[Left]] >= k && query(R[Left], R[Right], mid + 1, r, k)) return 1 ;
    return 0 ;
}
int main(){
    cin >> N >> M; for (i = 1; i <= N ; ++ i)  base[i] = qr() + ADD, aft[i] = base[i] ;
    sort (aft + 1, aft + N + 1), Len = unique(aft + 1, aft + N + 1) - (aft + 1) ;
    for (i = 1; i <= N ; ++ i) pos = lower_bound(aft + 1, aft + Len + 1, base[i]) - aft, T[i] = update(T[i - 1], 1, Len, pos) ;
    for (i = 1; i <= M ; ++ i){
        a = qr(), b = qr() ;
        register int l = 1, mid, r = b - a + 1, ans = 1 ;
        while (l <= r){
            mid = (l + r) >> 1 ;
            if (query(T[a - 1], T[b], 1, Len, mid)) ans = mid, l = mid + 1 ; 
            else r = mid - 1 ;
        }
        printf("%d\n", ans) ;
    }
}

最后是_rqy提的hack思路：