CF840D Destiny 主席树

😊 | Powered By HeartFireY

Problem Analysis 仍然是维护区间内数字出现的次数，然后在树上暴力查询左右子节点间的值，当碰到某个节点小于等于 r − l + 1 k \frac{r - l + 1}{k} kr−l+1​直接终止查询向父节点回溯。

Accepted 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