21.CF840D Destiny 可持久化权值线段树+二分查询

21.CF840D Destiny 可持久化权值线段树+二分查询

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定 n n n个元素， m m m次询问。

每次给出三个参数 l , r , k l,r,k l,r,k，询问区间 [ l , r ] [l,r] [l,r]内是否存在出现次数严格大于 r − l + 1 k \frac{r-l+1}{k} kr−l+1​的数。如果存在就输出最小的那个 a n s ans ans，否则输出 − 1 -1 −1

区间大于 k k k的数，于是想到用可持久化权值线段树解决，注意额外检查左右区间。

洛谷传送门：CF840D Destiny - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：D. Destiny (codeforces.com)

题目分析

做多了会发现，这种题的重点在于树上二分查询的边界条件及左右子树递归的策略。

对原序列建立可持久化权值线段树。查询时，左边的权值一定比右边的权值小，如果左边的出现个数大于 ⌊ r − l + 1 k ⌋ \lfloor \frac{r-l+1}{k} \rfloor ⌊kr−l+1​⌋ 就暴力向左子树递归查询。但注意，如果左子树满足条件，答案未必就在左子树，仍需要搜右子树：因为左边只是总次数满足条件。

因此左子树搜索失败时，向右找，如果可以的话，直到找到，就一定是最小值。

Code

#include 
#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  n >> m;
    for(int i = 1; i > a[i];
    for(int i = 1; i > l >> r >> k;
        ll tar = (r - l + 1) / k, ans = query(root[r], root[l - 1], 1, n, tar);
        if(ans == 1e18) cout