_pks 'w blog

_pks 'w blog

除了勇气,我什么都不缺。

题解 CF840D 【Destiny】

posted on 2019-03-22 20:10:39 | under 题解 |

比较推荐的一道主席树入门题。

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

然后…然后就没有然后了qwq

#include<cstdio>
#include<iostream>
#include<algorithm>
#define il inline
#define MAXN 500510
#define mid ((l + r) >> 1)

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

il int qr(){
    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;
}
il int build(int l, int r){
    int rt = ++ cnt ;
    sum[rt] = 0 ;
    if(l < r){
        L[rt] = build(l, mid) ;
        R[rt] = build(mid + 1, r) ;
    }
    return rt;
}
il int update(int last, int l, int r, int x){
    int rt = ++ cnt ;
    sum[rt] = sum[last] + 1 ;
    R[rt] = R[last] ;
    L[rt] = L[last] ;
    if (l < r){
        if (x <= mid) L[rt] = update(L[last], l, mid, x) ;
        else  R[rt] = update(R[last], mid + 1, r, x) ;
    }
    return rt ;
}
il int query(int Left, int Right, int l, int r, int k){
    if (l == r) return aft[l] ; int 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() ;
        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%d", &a, &b, &c) ; int k = (b - a + 1) / c ;
        cout << query(T[a - 1], T[b], 1, Len, k) << endl ; 
    }
    return 0 ; 
}