_皎月半洒花 的博客

_皎月半洒花 的博客

反抗命运的镇魂曲停歇之前,你绝对不可以说我懦弱,绝对不可以说我没有殊死一搏。

题解 P1997 【faebdc的烦恼】

posted on 2019-03-22 21:58:26 | under 题解 |

这是一篇主席树的题解。

我们思考主席树的本质,其实就是可以刨出一个区间 $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$ 思路: