21.CF840D Destiny 可持久化權值線段樹+二分查詢

個人Limitの線段樹題單題解主目錄：

給定個元素，次詢問。

每次給出三個參數，詢問區間内是否存在出現次數嚴格大于的數。如果存在就輸出最小的那個，否則輸出

區間大于的數，于是想到用可持久化權值線段樹解決，注意額外檢查左右區間。

洛谷傳送門：​​CF840D Destiny - 洛谷 | 計算機科學教育新生态 (luogu.com.cn)​​

CF傳送門：​​D. Destiny (codeforces.com)​​

題目分析

做多了會發現，這種題的重點在于樹上二分查詢的邊界條件及左右子樹遞歸的政策。

Code

#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int N = 5e5 + 10;

ll a[N], b[N];
ll tot, root[N << 5], sum[N << 5], lc[N << 5], rc[N << 5];

void update(int &rt, int pre, int l, int r, int k, int v){
    rt = ++tot, lc[rt] = lc[pre], rc[rt] = rc[pre], sum[rt] = sum[pre];
    if(l == r){
        sum[rt] += v;
        return;
    }
    int mid = l + r >> 1;
    if(k <= mid) update(lc[rt], lc[pre], l, mid, k, v);
    else update(rc[rt], rc[pre], mid + 1, r, k, v);
    sum[rt] = sum[lc[rt]] + sum[rc[rt]];
}

int query(int rt, int pre, int l, int r, int k){
    if(sum[rt] - sum[pre] <= k) return -1;
    if(l == r) return l;
    ll res = 1e18;
    ll mid = l + r >> 1;
    if(sum[lc[rt]] - sum[lc[pre]] > k){
        ll ans = query(lc[rt], lc[pre], l, mid, k);
        if(ans > 0) res = min(res, ans);
    }
    if(sum[rc[rt]] - sum[rc[pre]] > k){
        ll ans = query(rc[rt], rc[pre], mid + 1, r, k);
        if(ans > 0) res = min(res, ans);
    }
    return res;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ll n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) update(root[i], root[i - 1], 1, n, a[i], 1);
    while(m--){
        ll l, r, k; cin >> l >> r >> k;
        ll tar = (r - l + 1) / k, ans = query(root[r], root[l - 1], 1, n, tar);
        if(ans == 1e18) cout << -1 << endl;
        else cout << ans << endl;
    }
    return 0;
}